We propose ECPv2, a scalable and theoretically grounded algorithm for global optimization of Lipschitz continuous functions with unknown Lipschitz constants. Building on the Every Call is Precious (ECP) framework, which ensures that each accepted function evaluation is potentially informative, ECPv2 addresses key limitations of ECP, including high computational cost and overly conservative early behavior. ECPv2 introduces three innovations: (i) an adaptive lower bound that prevents vacuous acceptance regions, (ii) a memory mechanism that restricts comparisons to a fixed-size subset of past evaluations, and (iii) a fixed random projection that accelerates distance computations in high dimensions. We theoretically show that ECPv2 retains ECP’s regret guarantees and expands the acceptance region with high probability. Extensive experiments and ablation studies empirically validate these findings. Using principled hyperparameter settings, we evaluate ECPv2 across a wide range of nonconvex optimization problems and find that it consistently matches or outperforms leading optimizers while significantly reducing wall clock time.

We study a generalization of the widely studied discrete influence maximization problem. We consider that instead of marketers using a budget to send free products to a few influencers, they can provide discounts to partly incentivize a larger set of influencers with the same budget. We show that this problem is an instance of maximizing the multilinear extension of a monotone submodular set function subject to an L1 constraint and characterize its optimal solution in terms of the solutions to the discrete influence maximization problem. We then use this characterization to propose and analyze an efficient (1 - 1/e)-approximation algorithm. We also show that with negligible additional work, this algorithm also allows the marketer to evaluate cost-benefit trade-offs over a range of budgets. Furthermore, we performed small-scale experiments on synthetic and real-world social networks to demonstrate our optimal solution characterization and greedy approximation. We also performed large-scale experiments on real-world social networks to show the performance and scalability of our method in contrast to methods proposed for other generalizations of influence maximization. Moreover, we demonstrated the practicality of our method in evaluating the cost-benefit tradeoffs involving budget selection for desired influence and profit maximization.

The alignment of large language models (LLMs) with human values is critical as these models become increasingly integrated into various societal and decision-making processes. Traditional methods, such as reinforcement learning from human feedback (RLHF), achieve alignment by fine-tuning model parameters, but these approaches are often computationally expensive and impractical when models are frozen or inaccessible for parameter modification. In contrast, prompt optimization is a viable alternative to RLHF for LLM alignment. While the existing literature has shown empirical promise of prompt optimization, its theoretical underpinning remains under-explored. We address this gap by formulating prompt optimization as an optimization problem and try to provide theoretical insights into the optimality of such a framework. To analyze the performance of the prompt optimization, we study theoretical suboptimality bounds and provide insights in terms of how prompt optimization depends upon the given prompter and target model. We also provide empirical validation through experiments on various datasets, demonstrating that prompt optimization can effectively align LLMs, even when parameter fine-tuning is not feasible.

Optimizing expensive, non-convex, black-box Lipschitz continuous functions presents significant challenges, particularly when the Lipschitz constant of the underlying function is unknown. Such problems often demand numerous function evaluations to approximate the global optimum, which can be prohibitive in terms of time, energy, or resources. In this work, we introduce Every Call is Precious (ECP), a novel global optimization algorithm that minimizes unpromising evaluations by strategically focusing on potentially optimal regions. Unlike previous approaches, ECP eliminates the need to estimate the Lipschitz constant, thereby avoiding additional function evaluations. ECP guarantees no-regret performance for infinite evaluation budgets and achieves minimax-optimal regret bounds within finite budgets. Extensive ablation studies validate the algorithm’s robustness, while empirical evaluations show that ECP outperforms 10 benchmark algorithms—including Lipschitz, Bayesian, bandits, and evolutionary methods—across 30 multi-dimensional non-convex synthetic and real-world optimization problems, which positions ECP as a competitive approach for global optimization.

We present two Policy Gradient-based algorithms with general parametrization in the context of infinite-horizon average reward Markov Decision Process (MDP). The first one employs Implicit Gradient Transport for variance reduction, ensuring an expected regret of the order $\tilde{\mathcal{O}}(T^{2/3})$. The second approach, rooted in Hessian-based techniques, ensures an expected regret of the order $\tilde{\mathcal{O}}(\sqrt{T})$. These results significantly improve the state-of-the-art $\tilde{\mathcal{O}}(T^{3/4})$ regret and achieve the theoretical lower bound. We also show that the average-reward function is approximately $L$-smooth, a result that was previously assumed in earlier works.

As rapidly growing AI computational demands accelerate the need for new hardware installation and maintenance, this work explores optimal data center resource management by balancing operational efficiency with fault tolerance through strategic rack positioning considering diverse resources and locations. Traditional mixed-integer programming (MIP) approaches often struggle with scalability, while heuristic methods may result in significant sub-optimality. To address these issues, this paper presents a novel two-tier optimization framework using a high-level deep reinforcement learning (DRL) model to guide a low-level gradient-based heuristic for local search. The high-level DRL agent employs Leader Reward for optimal rack type ordering, and the low-level heuristic efficiently maps racks to positions, minimizing movement counts and ensuring fault-tolerant resource distribution. This approach allows scalability to over 100,000 positions and 100 rack types. Our method outperformed the gradient-based heuristic by 7% on average and the MIP solver by over 30% in objective value. It achieved a 100% success rate versus MIP's 97.5% (within a 20-minute limit), completing in just 2 minutes compared to MIP's 1630 minutes (i.e., almost 4 orders of magnitude improvement). Unlike the MIP solver, which showed performance variability under time constraints and high penalties, our algorithm consistently delivered stable, efficient results—an essential feature for large-scale data center management.

To improve the efficiency of reinforcement learning (RL), we propose a novel asynchronous federated reinforcement learning (FedRL) framework termed AFedPG, which constructs a global model through collaboration among $N$ agents using policy gradient (PG) updates. To address the challenge of lagged policies in asynchronous settings, we design a delay-adaptive lookahead technique *specifically for FedRL* that can effectively handle heterogeneous arrival times of policy gradients. We analyze the theoretical global convergence bound of AFedPG, and characterize the advantage of the proposed algorithm in terms of both the sample complexity and time complexity. Specifically, our AFedPG method achieves $\mathcal{O}(\frac{{\epsilon}^{-2.5}}{N})$ sample complexity for global convergence at each agent on average. Compared to the single agent setting with $\mathcal{O}(\epsilon^{-2.5})$ sample complexity, it enjoys a linear speedup with respect to the number of agents. Moreover, compared to synchronous FedPG, AFedPG improves the time complexity from $\mathcal{O}(\frac{t_{\max}}{N})$ to $\mathcal{O}({\sum_{i=1}^{N} \frac{1}{t_{i}}})^{-1}$, where $t_{i}$ denotes the time consumption in each iteration at agent $i$, and $t_{\max}$ is the largest one. The latter complexity $\mathcal{O}({\sum_{i=1}^{N} \frac{1}{t_{i}}})^{-1}$ is always smaller than the former one, and this improvement becomes significant in large-scale federated settings with heterogeneous computing powers ($t_{\max}\gg t_{\min}$). Finally, we empirically verify the improved performance of AFedPG in four widely used MuJoCo environments with varying numbers of agents. We also demonstrate the advantages of AFedPG in various computing heterogeneity scenarios.

We address the problem of quantum reinforcement learning (QRL) under model-free settings with quantum oracle access to the Markov Decision Process (MDP). This paper introduces a Quantum Natural Policy Gradient (QNPG) algorithm, which replaces the random sampling used in classical Natural Policy Gradient (NPG) estimators with a deterministic gradient estimation approach, enabling seamless integration into quantum systems. While this modification introduces a bounded bias in the estimator, the bias decays exponentially with increasing truncation levels. This paper demonstrates that the proposed QNPG algorithm achieves a sample complexity of $\tilde{\mathcal{O}}(\epsilon^{-1.5})$ for queries to the quantum oracle, significantly improving the classical lower bound of $\tilde{\mathcal{O}}(\epsilon^{-2})$ for queries to the MDP.

This work examines average-reward reinforcement learning with general policy parametrization. Existing state-of-the-art (SOTA) guarantees for this problem are either suboptimal or hindered by several challenges, including poor scalability with respect to the size of the state-action space, high iteration complexity, and a significant dependence on knowledge of mixing times and hitting times. To address these limitations, we propose a Multi-level Monte Carlo-based Natural Actor-Critic (MLMC-NAC) algorithm. Our work is the first to achieve a global convergence rate of $\tilde{\mathcal{O}}(1/\sqrt{T})$ for average-reward Markov Decision Processes (MDPs) (where $T$ is the horizon length), using an Actor-Critic approach. Moreover, the convergence rate does not scale with the size of the state space, therefore even being applicable to infinite state spaces.

This paper investigates the potential of quantum acceleration in addressing infinite horizon Markov Decision Processes (MDPs) to enhance average reward outcomes. We introduce an innovative quantum framework for the agent's engagement with an unknown MDP, extending the conventional interaction paradigm. Our approach involves the design of an optimism-driven tabular Reinforcement Learning algorithm that harnesses quantum signals acquired by the agent through efficient quantum mean estimation techniques. Through thorough theoretical analysis, we demonstrate that the quantum advantage in mean estimation leads to exponential advancements in regret guarantees for infinite horizon Reinforcement Learning. Specifically, the proposed Quantum algorithm achieves a regret bound of $\tilde{\mathcal{O}}(1)$\footnote{$\tilde{\mathcal{O}}(\cdot)$ conceals logarithmic terms of $T$.}, a significant improvement over the $\tilde{\mathcal{O}}(\sqrt{T})$ bound exhibited by classical counterparts, where $T$ is the length of the time horizon.

Skills are effective temporal abstractions established for sequential decision making, which enable efficient hierarchical learning for long-horizon tasks and facilitate multi-task learning through their transferability. Despite extensive research, research gaps remain in multi-agent scenarios, particularly for automatically extracting subgroup coordination patterns in a multi-agent task. In this case, we propose two novel auto-encoder schemes: VO-MASD-3D and VO-MASD-Hier, to simultaneously capture subgroup- and temporal-level abstractions and form multi-agent skills, which firstly solves the aforementioned challenge. An essential algorithm component of these schemes is a dynamic grouping function that can automatically detect latent subgroups based on agent interactions in a task. Further, our method can be applied to offline multi-task data, and the discovered subgroup skills can be transferred across relevant tasks without retraining. Empirical evaluations on StarCraft tasks indicate that our approach significantly outperforms existing hierarchical multi-agent reinforcement learning (MARL) methods. Moreover, skills discovered using our method can effectively reduce the learning difficulty in MARL scenarios with delayed and sparse reward signals. The codebase is available at: https://github.com/LucasCJYSDL/VOMASD.

By framing reinforcement learning as a sequence modeling problem, recent work has enabled the use of generative models, such as diffusion models, for planning. While these models are effective in predicting long-horizon state trajectories in deterministic environments, they face challenges in dynamic settings with moving obstacles. Effective collision avoidance demands continuous monitoring and adaptive decision-making. While re-planning at every time step could ensure safety, it introduces substantial computational overhead due to the repetitive prediction of overlapping state sequences—a process that is particularly costly with diffusion models, known for their intensive iterative sampling procedure. We propose an adaptive generative planning approach that dynamically adjusts re-planning frequency based on the uncertainty of action predictions. Our method minimizes the need for frequent, computationally expensive, and redundant re-planning while maintaining robust collision avoidance performance. In experiments, we obtain a 13.5% increase in the mean trajectory length and 12.7% increase in mean reward over long-horizon planning, indicating a reduction in collision rates, and improved ability to navigate the environment safely.

Actor-Critic methods are widely used for their scalability, yet existing theoretical guarantees for infinite-horizon average-reward Markov Decision Processes (MDPs) often rely on restrictive ergodicity assumptions. We propose NAC-B, a Natural Actor-Critic with Batching, that achieves order-optimal regret of \$\tilde{O}(\sqrt{T})\$ in infinite-horizon average-reward MDPs under the unichain assumption, which permits both transient states and periodicity. This assumption is among the weakest under which the classic policy gradient theorem remains valid for average-reward settings. NAC-B employs function approximation for both the actor and the critic, enabling scalability to problems with large state and action spaces. The use of batching in our algorithm helps mitigate potential periodicity in the MDP and reduces stochasticity in gradient estimates, and our analysis formalizes these benefits through the introduction of the constants $C_{\text{hit}}$ and $C_{\text{tar}}$, which characterize the rate at which empirical averages over Markovian samples converge to the stationary distribution.

Bilevel reinforcement learning (BRL) has emerged as a powerful framework for aligning generative models, yet its theoretical foundations, especially sample complexity bounds, remain relatively underexplored. In this work, we present the first sample complexity bound for BRL, establishing a rate of $\tilde{\mathcal{O}}(\epsilon^{-3})$ in continuous state-action spaces. Traditional MDP analysis techniques do not extend to BRL due to its nested structure and non-convex lower-level problems. We overcome these challenges by leveraging the Polyak-Łojasiewicz (PL) condition and the MDP structure to obtain closed-form gradients, enabling tight sample complexity analysis. Our analysis also extends to general bi-level optimization settings with non-convex lower levels, where we achieve state-of-the-art sample complexity results of $\tilde{\mathcal{O}}(\epsilon^{-3})$ improving upon existing bounds of $\tilde{\mathcal{O}}(\epsilon^{-6})$. Additionally, we address the computational bottleneck of hypergradient estimation by proposing a fully first-order, Hessian-free algorithm suitable for large-scale problems.

This paper presents novel contributions to the field of online optimization, particularly focusing on the adaptation of algorithms from concave optimization to more challenging classes of functions. Key contributions include the introduction of uniform wrappers, a class of meta-algorithms that could be used for algorithmic conversions such as converting algorithms for convex optimization into those for quadratizable optimization. Moreover, we propose a guideline that, given a base algorithm $\mathcal{A}$ for concave optimization and a uniform wrapper $\mathcal{W}$, describes how to convert a proof of the regret bound of $\mathcal{A}$ in the concave setting into a proof of the regret bound of $\mathcal{W}(\mathcal{A})$ for quadratizable setting. Through this framework, the paper demonstrates improved regret guarantees for various classes of DR-submodular functions under zeroth-order feedback. Furthermore, the paper extends zeroth-order online algorithms to bandit feedback and offline counterparts, achieving notable improvements in regret/sample complexity compared to existing approaches.

Spatial transcriptomics technologies can be used to align transcriptomes with histopathological morphology, presenting exciting new opportunities for biomolecular discovery. Using spatial transcriptomic gene expression and corresponding histology data, we construct a novel framework, GeneFlow, to map single- and multi-cell gene expression onto paired cellular images. By combining an attention-based RNA encoder with a conditional UNet guided by rectified flow, we generate high-resolution images with different staining methods (e.g., H\&E, DAPI) to highlight various cellular/ tissue structures. Rectified flow with high-order ODE solvers creates a continuous, bijective mapping between expression and image manifolds, addressing the many-to-one relationship inherent in this problem. Our method enables the generation of realistic cellular morphology features and spatially resolved intercellular interactions under genetic or chemical perturbations. This enables minimally invasive disease diagnosis by revealing dysregulated patterns in imaging phenotypes. Our rectified flow based method outperforms diffusion methods and baselines in all experiments. Code is available at https://github.com/wangmengbo/GeneFlow.

This paper investigates infinite-horizon average reward Constrained Markov Decision Processes (CMDPs) under general parametrized policies with smooth and bounded policy gradients. We propose a Primal-Dual Natural Actor-Critic algorithm that adeptly manages constraints while ensuring a high convergence rate. In particular, our algorithm achieves global convergence and constraint violation rates of $\tilde{\mathcal{O}}(1/\sqrt{T})$ over a horizon of length $T$ when the mixing time, $\tau_{\mathrm{mix}}$, is known to the learner. In absence of knowledge of $\tau_{\mathrm{mix}}$, the achievable rates change to $\tilde{\mathcal{O}}(1/T^{0.5-\epsilon})$ provided that $T \geq \tilde{\mathcal{O}}\left(\tau_{\mathrm{mix}}^{2/\epsilon}\right)$. Our results match the theoretical lower bound for Markov Decision Processes and establish a new benchmark in the theoretical exploration of average reward CMDPs.

We present the first finite-sample analysis of policy evaluation in robust average-reward Markov Decision Processes (MDPs). Prior work in this setting have established only asymptotic convergence guarantees, leaving open the question of sample complexity. In this work, we address this gap by showing that the robust Bellman operator is a contraction under a carefully constructed semi-norm, and developing a stochastic approximation framework with controlled bias. Our approach builds upon Multi-Level Monte Carlo (MLMC) techniques to estimate the robust Bellman operator efficiently. To overcome the infinite expected sample complexity inherent in standard MLMC, we introduce a truncation mechanism based on a geometric distribution, ensuring a finite expected sample complexity while maintaining a small bias that decays exponentially with the truncation level. Our method achieves the order-optimal sample complexity of $\tilde{\mathcal{O}}(\epsilon^{-2})$ for robust policy evaluation and robust average reward estimation, marking a significant advancement in robust reinforcement learning theory.

This paper addresses the challenge of achieving order-optimal sample complexity in reinforcement learning for discounted Markov Decision Processes (MDPs) with general policy parameterization and multi-layer neural network critics. Existing approaches either fail to achieve the optimal rate or assume a linear critic. We introduce Natural Actor-Critic with Data Drop (NAC-DD) algorithm, which integrates Natural Policy Gradient methods with a Data Drop technique to mitigate statistical dependencies inherent in Markovian sampling. NAC-DD achieves an optimal sample complexity of $\tilde{\mathcal{O}}(1/\epsilon^2)$, marking a significant improvement over the previous state-of-the-art guarantee of $\tilde{O}(1/\epsilon^3)$. The algorithm employs a multi-layer neural network critic with differentiable activation functions, aligning with real-world applications where tabular policies and linear critics are insufficient. Our work represents the first to achieve order-optimal sample complexity for actor-critic methods with neural function approximation, continuous state and action spaces, and Markovian sampling. Empirical evaluations on benchmark tasks confirm the theoretical findings, demonstrating the practical efficacy of the proposed method.

Recent advancements in generative models have established state-of-the-art benchmarks in the generation of molecules and novel drug candidates. Despite these successes, a significant gap persists between generative models and the utilization of extensive biomedical knowledge, often systematized within knowledge graphs, whose potential to inform and enhance generative processes has not been realized. In this paper, we present a novel approach that bridges this divide by developing a framework for knowledge-enhanced generative models called KARL. We develop a scalable methodology to extend the functionality of knowledge graphs while preserving semantic integrity, and incorporate this contextual information into a generative framework to guide a diffusion-based model. The integration of knowledge graph embeddings with our generative model furnishes a robust mechanism for producing novel drug candidates possessing specific characteristics while ensuring validity and synthesizability. KARL outperforms state-of-the-art generative models on both unconditional and targeted generation tasks.

Machine learning, particularly through advanced imaging techniques such as three-dimensional Magnetic Resonance Imaging (MRI), has significantly improved medical diagnostics. This is especially critical for diagnosing complex conditions like Alzheimer's disease. Our study introduces Triamese-ViT, an innovative Tri-structure of Vision Transformers (ViTs) that incorporates a built-in interpretability function, it has structure-aware explainability that allows for the identification and visualization of key features or regions contributing to the prediction, integrates information from three perspectives to enhance brain age estimation. This method not only increases accuracy but also improves interoperability with existing techniques. When evaluated, Triamese-ViT demonstrated superior performance and produced insightful attention maps. We applied these attention maps to the analysis of natural aging and the diagnosis of Autism Spectrum Disorder (ASD). The results aligned with those from occlusion analysis, identifying the Cingulum, Rolandic Operculum, Thalamus, and Vermis as important regions in normal aging, and highlighting the Thalamus and Caudate Nucleus as key regions for ASD diagnosis.

Fueled by Metaverse, 360° video streaming has seen tremendous growth in the past years. However, our measurement reveals that current 360° streaming systems suffer from a dilemma that severely limits QoE. On the one hand, viewport prediction requires the shortest possible prediction distance for high predicting accuracy; On the other hand, video transmission requires more buffered data to compensate for bandwidth fluctuations otherwise substantial playback rebuffering would be incurred. There is so far no existing method that can break this dilemma so the QoE optimization for 360° video streaming was naturally bottlenecked. This work is the first attempt to tackle this challenge by developing QUTA – a novel learning-based streaming system. Specifically, according to our measurement, three kinds of internal streaming parameters have significant impacts on the prediction distance, namely, download pause, data rate threshold, and playback rate. On top of this, we design a new long-term-planning (LTP) continuous control deep reinforcement learning method that tunes the parameters dynamically based on the network condition and the streaming context. Extensive evaluations based on real system prototypes show that QUTA not only improves the prediction accuracy and QoE performance by up to 68.4% but also exhibits strong temporal and spatial robustness.

Online optimization of resource management for large-scale data centers and infrastructures to meet dynamic capacity reservation demands and various practical constraints (e.g., feasibility and robustness) is a very challenging problem. Mixed Integer Programming (MIP) approaches suffer from recognized limitations in such a dynamic environment, while learning-based approaches may face with prohibitively large state/action spaces. To this end, this paper presents a novel two-tiered online optimization to enable a learning-based Resource Allowance System (RAS). To solve optimal server-to-reservation assignment in RAS in an online fashion, the proposed solution leverages a reinforcement learning (RL) agent to make high-level decisions, e.g., how much resource to select from the Main Switch Boards (MSBs), and then a low-level Mixed Integer Linear Programming (MILP) solver to generate the local server-to-reservation mapping, conditioned on the RL decisions. We take into account fault tolerance, server movement minimization, and network affinity requirements and apply the proposed solution to large-scale RAS problems. To provide interpretability, we further train a decision tree model to explain the learned policies and to prune unreasonable corner cases at the low-level MILP solver, resulting in further performance improvement. Extensive evaluations show that our two-tiered solution outperforms baselines such as pure MIP solver by over 15% while delivering$100\times $speedup in computation.

In this paper, we consider an infinite horizon average reward Markov Decision Process (MDP). Distinguishing itself from existing works within this context, our approach harnesses the power of the general policy gradient-based algorithm, liberating it from the constraints of assuming a linear MDP structure. We propose a vanilla policy gradient-based algorithm and show its global convergence property. We then prove that the proposed algorithm has O(T^3/4) regret. Remarkably, this paper marks a pioneering effort by presenting the first exploration into regret bound computation for the general parameterized policy gradient algorithm in the context of average reward scenarios.

We propose a novel combinatorial stochastic-greedy bandit (SGB) algorithm for combinatorial multi-armed bandit problems when no extra information other than the joint reward of the selected set of n arms at each time step t in [T] is observed. SGB adopts an optimized stochastic-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms. Unlike existing methods that explore the entire set of unselected base arms during each selection step, our SGB algorithm samples only an optimized proportion of unselected arms and selects actions from this subset. We prove that our algorithm achieves a (1-1/e)-regret bound of O(n^(1/3) k^(2/3) T^(2/3) log(T)^(2/3)) for monotone stochastic submodular rewards, which outperforms the state-of-the-art in terms of the cardinality constraint k. Furthermore, we empirically evaluate the performance of our algorithm in the context of online constrained social influence maximization. Our results demonstrate that our proposed approach consistently outperforms the other algorithms, increasing the performance gap as k grows.

Federated learning, an emerging machine learning paradigm, enables clients to collaboratively train a model without exchanging local data. Clients participating in the training process significantly impact the convergence rate, learning efficiency, and model generalization. We propose a novel approach, client filtering, to improve model generalization and optimize client participation and training. The proposed method periodically filters available clients to identify a subset that maximizes a combinatorial objective function with an efficient greedy filtering algorithm. Thus, the clients are assessed as a combination rather than individually. We theoretically analyze the convergence of federated learning with client filtering in heterogeneous settings and evaluate its performance across diverse vision and language tasks, including realistic scenarios with time-varying client availability. Our empirical results demonstrate several benefits of our approach, including improved learning efficiency, faster convergence, and up to 10% higher test accuracy than training without client filtering.

This paper introduces unified projection-free Frank-Wolfe type algorithms for adversarial continuous DR-submodular optimization, spanning scenarios such as full information and (semi-)bandit feedback, monotone and non-monotone functions, different constraints, and types of stochastic queries. For every problem considered in the non-monotone setting, the proposed algorithms are either the first with proven sub-linear $\alpha$-regret bounds or have better $\alpha$-regret bounds than the state of the art, where $\alpha$ is a corresponding approximation bound in the offline setting. In the monotone setting, the proposed approach gives state-of-the-art sub-linear $\alpha$-regret bounds among projection-free algorithms in 7 of the 8 considered cases while matching the result of the remaining case. Additionally, this paper addresses semi-bandit and bandit feedback for adversarial DR-submodular optimization, advancing the understanding of this optimization area.

In this paper, we revisit the problem of sparse linear regression in the local differential privacy (LDP) model. Existing research in the non-interactive and sequentially local models has focused on obtaining the lower bounds for the case where the underlying parameter is $1$-sparse, and extending such bounds to the more general $k$-sparse case has proven to be challenging. Moreover, it is unclear whether efficient non-interactive LDP (NLDP) algorithms exist. To address these issues, we first consider the problem in the $\epsilon$ non-interactive LDP model and provide a lower bound of $\Omega(\frac{\sqrt{dk\log d}}{\sqrt{n}\epsilon})$ on the $\ell_2$-norm estimation error for sub-Gaussian data, where $n$ is the sample size and $d$ is the dimension of the space. We propose an innovative NLDP algorithm, the very first of its kind for the problem. As a remarkable outcome, this algorithm also yields a novel and highly efficient estimator as a valuable by-product. Our algorithm achieves an upper bound of $\tilde{O}({\frac{d\sqrt{k}}{\sqrt{n}\epsilon}})$ for the estimation error when the data is sub-Gaussian, which can be further improved by a factor of $O(\sqrt{d})$ if the server has additional public but unlabeled data. For the sequentially interactive LDP model, we show a similar lower bound of $\Omega({\frac{\sqrt{dk}}{\sqrt{n}\epsilon}})$. As for the upper bound, we rectify a previous method and show that it is possible to achieve a bound of $\tilde{O}(\frac{k\sqrt{d}}{\sqrt{n}\epsilon})$. Our findings reveal fundamental differences between the non-private case, central DP model, and local DP model in the sparse linear regression problem.

This paper introduces a federated learning framework tailored for online combinatorial optimization with bandit feedback. In this setting, agents select subsets of arms, observe noisy rewards for these subsets without accessing individual arm information, and can cooperate and share information at specific intervals. Our framework transforms any offline resilient single-agent $(\alpha-\epsilon)$-approximation algorithm—having a complexity of $\tilde{\mathcal{O}}\left(\frac{\psi}{\epsilon^\beta}\right)$, where the logarithm is omitted, for some function $\psi$ and constant $\beta$—into an online multi-agent algorithm with $m$ communicating agents and an $\alpha$-regret of no more than $\tilde{\mathcal{O}}\left(m^{-\frac{1}{3+\beta}} \psi^\frac{1}{3+\beta} T^\frac{2+\beta}{3+\beta}\right)$. Our approach not only eliminates the $\epsilon$ approximation error but also ensures sublinear growth with respect to the time horizon $T$ and demonstrates a linear speedup with an increasing number of communicating agents. Additionally, the algorithm is notably communication-efficient, requiring only a sublinear number of communication rounds, quantified as $\tilde{\mathcal{O}}\left(\psi T^\frac{\beta}{\beta+1}\right)$. Furthermore, the framework has been successfully applied to online stochastic submodular maximization using various offline algorithms, yielding the first results for both single-agent and multi-agent settings and recovering specialized single-agent theoretical guarantees. We empirically validate our approach to a stochastic data summarization problem, illustrating the effectiveness of the proposed framework, even in single-agent scenarios.

In complex environments with large discrete action spaces, effective decision-making is critical in reinforcement learning (RL). Despite the widespread use of value-based RL approaches like Q-learning, they come with a computational burden, necessitating the maximization of a value function over all actions in each iteration. This burden becomes particularly challenging when addressing large-scale problems and using deep neural networks as function approximators. In this paper, we present stochastic value-based RL approaches which, in each iteration, as opposed to optimizing over the entire set of $n$ actions, only consider a variable stochastic set of a sublinear number of actions, possibly as small as $\mathcal{O}(\log(n))$. The presented stochastic value-based RL methods include, among others, Stochastic Q-learning, StochDQN, and StochDDQN, all of which integrate this stochastic approach for both value-function updates and action selection. The theoretical convergence of Stochastic Q-learning is established, while an analysis of stochastic maximization is provided. Moreover, through empirical validation, we illustrate that the various proposed approaches outperform the baseline methods across diverse environments, including different control problems, achieving near-optimal average returns in significantly reduced time.

The current state-of-the-art theoretical analysis of Actor-Critic (AC) algorithms significantly lags in addressing the practical aspects of AC implementations. This crucial gap needs bridging to bring the analysis in line with practical implementations of AC. To address this, we advocate for considering the MMCLG criteria: **M**ulti-layer neural network parametrization for actor/critic, **M**arkovian sampling, **C**ontinuous state-action spaces, the performance of the **L**ast iterate, and **G**lobal optimality. These aspects are practically significant and have been largely overlooked in existing theoretical analyses of AC algorithms. In this work, we address these gaps by providing the first comprehensive theoretical analysis of AC algorithms that encompasses all five crucial practical aspects (covers MMCLG criteria). We establish global convergence sample complexity bounds of $\tilde{\mathcal{O}}\left( \epsilon^{-3} \right)$. We achieve this result through our novel use of the weak gradient domination property of MDP's and our unique analysis of the error in critic estimation.

In the context of average-reward reinforcement learning, the requirement for oracle knowledge of the mixing time, a measure of the duration a Markov chain under a fixed policy needs to achieve its stationary distribution, poses a significant challenge for the global convergence of policy gradient methods. This requirement is particularly problematic due to the difficulty and expense of estimating mixing time in environments with large state spaces, leading to the necessity of impractically long trajectories for effective gradient estimation in practical applications. To address this limitation, we consider the Multi-level Actor-Critic (MAC) framework, which incorporates a Multi-level Monte-Carlo (MLMC) gradient estimator. With our approach, we effectively alleviate the dependency on mixing time knowledge, a first for average-reward MDPs global convergence. Furthermore, our approach exhibits the tightest available dependence of $\mathcal{O}(\sqrt{\tau_{mix}})$ known from prior work. With a 2D grid world goal-reaching navigation experiment, we demonstrate that MAC outperforms the existing state-of-the-art policy gradient-based method for average reward settings.

This paper explores the realm of infinite horizon average reward Constrained Markov Decision Processes (CMDPs). To the best of our knowledge, this work is the first to delve into the regret and constraint violation analysis of average reward CMDPs with a general policy parametrization. To address this challenge, we propose a primal dual-based policy gradient algorithm that adeptly manages the constraints while ensuring a low regret guarantee toward achieving a global optimal policy. In particular, our proposed algorithm achieves $\tilde{\mathcal{O}}({T}^{4/5})$ objective regret and $\tilde{\mathcal{O}}({T}^{4/5})$ constraint violation bounds.

We consider a constrained Markov Decision Problem (CMDP) where the goal of an agent is to maximize the expected discounted sum of rewards over an infinite horizon while ensuring that the expected discounted sum of costs exceeds a certain threshold. Building on the idea of momentum-based acceleration, we develop the Primal-Dual Accelerated Natural Policy Gradient (PD-ANPG) algorithm that ensures an $\epsilon$ global optimality gap and $\epsilon$ constraint violation with $\tilde{\mathcal{O}}((1-\gamma)^{-7}\epsilon^{-2})$ sample complexity for general parameterized policies where $\gamma$ denotes the discount factor. This improves the state-of-the-art sample complexity in general parameterized CMDPs by a factor of $\mathcal{O}((1-\gamma)^{-1}\epsilon^{-2})$ and achieves the theoretical lower bound in $\epsilon^{-1}$.

In this paper, we consider the problem of online monotone DR-submodular maximization subject to long-term stochastic constraints. Specifically, at each round $t\in [T]$, after committing an action $\mathbf{x}_t$, a random reward $f_t(\mathbf{x}_t)$ and an unbiased gradient estimate of the point $\widetilde{\nabla}f_t(\mathbf{x}_t)$ (semi-bandit feedback) are revealed. Meanwhile, a budget of $g_t(\mathbf{x}_t)$, which is linear and stochastic, is consumed of its total allotted budget $B_T$. We propose a gradient ascent based algorithm that achieves $\frac{1}{2}$-regret of $\mathcal{O}(\sqrt{T})$ with $\mathcal{O}(T^{3/4})$ constraint violation with high probability. Moreover, when first-order full-information feedback is available, we propose an algorithm that achieves $(1-1/e)$-regret of $\mathcal{O}(\sqrt{T})$ with $\mathcal{O}(T^{3/4})$ constraint violation. These algorithms significantly improve over the state-of-the-art in terms of query complexity.

This paper introduces the notion of upper-linearizable/quadratizable functions, a class that extends concavity and DR-submodularity in various settings, including monotone and non-monotone cases over different types of convex sets. A general meta-algorithm is devised to convert algorithms for linear/quadratic maximization into ones that optimize upper-linearizable/quadratizable functions, offering a unified approach to tackling concave and DR-submodular optimization problems. The paper extends these results to multiple feedback settings, facilitating conversions between semi-bandit/first-order feedback and bandit/zeroth-order feedback, as well as between first/zeroth-order feedback and semi-bandit/bandit feedback. Leveraging this framework, new algorithms are derived using existing results as base algorithms for convex optimization, improving upon state-of-the-art results in various cases. Dynamic and adaptive regret guarantees are obtained for DR-submodular maximization, marking the first algorithms to achieve such guarantees in these settings. Notably, the paper achieves these advancements with fewer assumptions compared to existing state-of-the-art results, underscoring its broad applicability and theoretical contributions to non-convex optimization.

This paper presents a Deep Reinforcement Learning (DRL) based Internet of Things (IoT)-enabled Prism blockchain. The recent advancements in the field of IoT motivate the development of a secure infrastructure for storing and sharing vast amounts of data. Blockchain, a distributed and immutable ledger, is best known as a potential solution to data security and privacy for the IoT. The scalability of blockchain, which should optimize the throughput and handle the dynamics of the IoT environment, becomes a challenge due to the enormous amount of IoT data. The critical challenge in scaling blockchain is to guarantee decentralization, latency, and security of the system while optimizing the transaction throughput. This paper presents a DRL-based performance optimization for blockchain-enabled IoT. We consider one of the recent promising blockchains, Prism, as the underlying blockchain system because of its good performance guarantees. We integrate the IoT data into Prism blockchain and optimize the performance of the system by leveraging the Proximal Policy Optimization (PPO) method. The DRL method helps to optimize the blockchain parameters like mining rate and mined blocks to adapt to the environment dynamics of the IoT system. Our results show that the proposed method can improve the throughput of Prism blockchain-based IoT systems while preserving Prism performance guarantees. Our scheme can achieve 1.5 times more system rewards than IoT-integrated Prism. In our experimental setup, the proposed scheme could improve the average throughput of the system by about 6,000 transactions per second compared to Prism.

Mean-Field Control (MFC) has recently been proven to be a scalable tool to approximately solve large-scale multi-agent reinforcement learning (MARL) problems. However, these studies are typically limited to unconstrained cumulative reward maximization framework. In this paper, we show that one can use the MFC approach to approximate the MARL problem even in the presence of constraints. Specifically, we prove that, an $N$-agent constrained MARL problem, with state, and action spaces of each individual agents being of sizes $|\mathcal{X}|$, and $|\mathcal{U}|$ respectively, can be approximated by an associated constrained MFC problem with an error, $e\triangleq \mathcal{O}\left([\sqrt{|\mathcal{X}|}+\sqrt{|\mathcal{U}|}]/\sqrt{N}\right)$. In a special case where the reward, cost, and state transition functions are independent of the action distribution of the population, we prove that the error can be improved to $e=\mathcal{O}(\sqrt{|\mathcal{X}|}/\sqrt{N})$. Also, we provide a Natural Policy Gradient based algorithm, and prove that it can solve the constrained MARL problem within an error of $\mathcal{O}(e)$ with a sample complexity of $\mathcal{O}(e^{-6})$.

Coded caching utilizes pre-fetching during off-peak hours and multi-casting for delivery in order to balance the traffic load in communication networks. Several works have studied the achievable peak and average rates under different conditions: variable file lengths or popularities, variable cache sizes, decentralized networks, etc. However, very few have considered the possibility of heterogeneous user profiles, despite modern content providers are investing heavily in categorizing users according to their habits and preferences. This paper proposes three coded caching schemes with uncoded pre-fetching for scenarios where end users are grouped into classes with different file demand sets (FDS). One scheme ignores the difference between the classes, another ignores the similarities between them and the third decouples the delivery of files common to all FDS from those unique to a single class. The transmission rates of the three schemes are compared with a lower bound to evaluate their gap to optimality, and with each other to show that each scheme can outperform the other two when certain conditions are met.

Sepsis, a life-threatening condition triggered by the body's exaggerated response to infection, demands urgent intervention to prevent severe complications. Existing machine learning methods for managing sepsis struggle in offline scenarios, exhibiting suboptimal performance with survival rates below 50%. This paper introduces thePosNegDM— “Reinforcement Learning with Positive and Negative Demonstrations for Sequential Decision-Making” framework utilizing an innovative transformer-based model and a feedback reinforcer to replicate expert actions while considering individual patient characteristics. A mortality classifier with 96.7% accuracy guides treatment decisions towards positive outcomes. ThePosNegDMframework significantly improves patient survival, saving 97.39% of patients, outperforming established machine learning algorithms (Decision Transformer and Behavioral Cloning) with survival rates of 33.4% and 43.5%, respectively. Additionally, ablation studies underscore the critical role of the transformer-based decision maker and the integration of a mortality classifier in enhancing overall survival rates. In summary, our proposed approach presents a promising avenue for enhancing sepsis treatment outcomes, contributing to improved patient care and reduced healthcare costs.

Imitation learning (IL) has been proposed to recover the expert policy from demonstrations. However, it would be difficult to learn a single monolithic policy for highly complex long-horizon tasks of which the expert policy usually contains subtask hierarchies. Therefore, hierarchical IL (HIL) has been developed to learn a hierarchical policy from expert demonstrations through explicitly modeling the activity structure in a task with the option framework. Existing HIL methods either overlook the causal relationship between the subtask structure and the learned policy, or fail to learn the high-level and low-level policy in the hierarchical framework in conjuncture, which leads to suboptimality. In this work, we propose a novel HIL algorithm-hierarchical adversarial inverse reinforcement learning (H-AIRL), which extends a state-of-the-art (SOTA) IL algorithm-AIRL, with the one-step option framework. Specifically, we redefine the AIRL objectives on the extended state and action spaces, and further introduce a directed information term to the objective function to enhance the causality between the low-level policy and its corresponding subtask. Moreover, we propose an expectation-maximization (EM) adaption of our algorithm so that it can be applied to expert demonstrations without the subtask annotations which are more accessible in practice. Theoretical justifications of our algorithm design and evaluations on challenging robotic control tasks are provided to show the superiority of our algorithm compared with SOTA HIL baselines. The codes are available at https://github.com/LucasCJYSDL/HierAIRL.

Federated Learning (FL) is an emerging domain in the broader context of artificial intelligence research. Methodologies pertaining to FL assume distributed model training, consisting of a collection of clients and a server, with the main goal of achieving optimal global model with restrictions on data sharing due to privacy concerns. It is worth highlighting that the diverse existing literature in FL mostly assume stationary data generation processes; such an assumption is unrealistic in real-world conditions where concept drift occurs due to, for instance, seasonal or period observations, faults in sensor measurements. In this paper, we introduce a multiscale algorithmic framework which combines theoretical guarantees of FedAvg and FedOMD algorithms in near stationary settings with a non-stationary detection and adaptation technique to ameliorate FL generalization performance in the presence of concept drifts. We present a multi-scale algorithmic framework leading to$\tilde {\mathcal {O}} (\min \{ \sqrt {LT}, \Delta ^{({1}/{3})}T^{({2}/{3})} + \sqrt {T} \})$dynamic regret for$T$rounds with an underlying general convex loss function, where$L$is the number of times non-stationary drifts occurred and$\Delta $is the cumulative magnitude of drift experienced within$T$rounds.

Federated learning (FedL) has emerged as a popular technique for distributing model training over a set of wireless devices, via iterative local updates (at devices) and global aggregations (at the server). In this paper, we develop parallel successive learning (PSL), which expands the FedL architecture along three dimensions: (i) Network, allowing decentralized cooperation among the devices via device-to-device (D2D) communications. (ii) Heterogeneity, interpreted at three levels: (ii-a) Learning: PSL considers heterogeneous number of stochastic gradient descent iterations with different mini-batch sizes at the devices; (ii-b) Data: PSL presumes a dynamic environment with data arrival and departure, where the distributions of local datasets evolve over time, captured via a new metric for model/concept drift. (ii-c) Device: PSL considers devices with different computation and communication capabilities. (iii) Proximity, where devices have different distances to each other and the access point. PSL considers the realistic scenario where global aggregations are conducted with idle times in-between them for resource efficiency improvements, and incorporates data dispersion and model dispersion with local model condensation into FedL. Our analysis sheds light on the notion of cold vs. warmed up models, and model inertia in distributed machine learning. We then propose network-aware dynamic model tracking to optimize the model learning vs. resource efficiency tradeoff, which we show is an NP-hard signomial programming problem. We finally solve this problem through proposing a general optimization solver. Our numerical results reveal new findings on the interdependencies between the idle times in-between the global aggregations, model/concept drift, and D2D cooperation configuration.

Robust network design, which aims to guarantee network availability under various failure scenarios while optimizing performance/cost objectives, has received significant attention. Existing approaches often rely on model-based mixed-integer optimization that is hard to scale or employ deep learning to solve specific engineering problems yet with limited generalizability. In this paper, we show that failure evaluation provides a common kernel to improve the tractability and scalability of existing solutions. By providing a neural network function approximation of this common kernel using graph attention networks, we develop a unified learning-based framework, FERN, for scalable Failure Evaluation and Robust Network design. FERN represents rich problem inputs as a graph and captures both local and global views by attentively performing feature extraction from the graph. It enables a broad range of robust network design problems, including robust network validation, network upgrade optimization, and fault-tolerant traffic engineering that are discussed in this paper, to be recasted with respect to the common kernel and thus computed efficiently using neural networks and over a small set of critical failure scenarios. Extensive experiments on real-world network topologies show that FERN can efficiently and accurately identify key failure scenarios for both OSPF and optimal routing scheme, and generalizes well to different topologies and input traffic patterns. It can speed up multiple robust network design problems by more than 80x, 200x, 10x, respectively with negligible performance gap.

This paper investigates the$(k,k)$fork-join scheduling scheme on a system of n parallel servers comprising both slow and fast servers. Tasks arriving in the system are divided into k sub-tasks and assigned to a random set of k servers, where each task can be assigned independently to a distinct slow or fast server with selection probability$p_{s}$or$1-p_{s}$, respectively. Our analysis demonstrates that the joint distribution of the stationary workload across any set of k queues becomes asymptotically independent as the number of servers n grows, with k scaling as$o\left ({{n^{\frac {1}{4}}}}\right)$. Under asymptotic independence, the limiting mean task completion time can be expressed as an integral. However, it is analytically challenging to compute the optimal selection probability$p_{s}^{\ast } $that minimizes this integral. To address this, we provide an upper bound on the limiting mean task completion time and identify the selection probability$\hat {p}_{s}$that minimizes this bound. We validate that this selection probability$\hat {p}_{s}$yields a near-optimal performance through numerical experiments.

We consider the problem of constrained Markov decision process (CMDP) in continuous state actions spaces where the goal is to maximize the expected cumulative reward subject to some constraints. We propose a novel Conservative Natural Policy Gradient Primal Dual Algorithm (CNPGPD) to achieve zero constraint violation while achieving state of the art convergence results for the objective value function. For general policy parametrization, we prove convergence of value function to global optimal upto an approximation error due to restricted policy class. We improve the sample complexity of existing constrained NPGPD algorithm. To the best of our knowledge, this is the first work to establish zero constraint violation with Natural policy gradient style algorithms for infinite horizon discounted CMDPs. We demonstrate the merits of proposed algorithm via experimental evaluations.

We investigate the problem of unconstrained combinatorial multi-armed bandits with full-bandit feedback and stochastic rewards for submodular maximization. Previous works investigate the same problem assuming a submodular and monotone reward function. In this work, we study a more general problem, i.e., when the reward function is not necessarily monotone, and the submodularity is assumed only in expectation. We propose Randomized Greedy Learning (RGL) algorithm and theoretically prove that it achieves a $\frac{1}{2}$-regret upper bound of $\tilde{\mathcal{O}}(n T^{\frac{2}{3}})$ for horizon $T$ and number of arms $n$. We also show in experiments that RGL empirically outperforms other full-bandit variants in submodular and non-submodular settings.

Few-shot learning has made impressive strides in addressing the crucial challenges of recognizing unknown samples from novel classes in target query sets and managing visual shifts between domains. However, existing techniques fall short when it comes to identifying target outliers under domain shifts by learning to reject pseudo-outliers from the source domain, resulting in an incomplete solution to both problems. To address these challenges comprehensively, we propose a novel approach called Domain Adaptive Few-Shot Open Set Recognition (DA-FSOS) and introduce a meta-learning-based architecture named DAFOS-Net. During training, our model learns a shared and discriminative embedding space while creating a pseudo-open-space decision boundary, given a fully-supervised source domain and a label-disjoint few-shot target domain. To enhance data density, we use a pair of conditional adversarial networks with tunable noise variances to augment both domains’ closed and pseudo-open spaces. Furthermore, we propose a domain-specific batch-normalized class prototypes alignment strategy to align both domains globally while ensuring class-discriminativeness through novel metric objectives. Our training approach ensures that DAFOS-Net can generalize well to new scenarios in the target domain. We present three benchmarks for DA-FSOS based on the Office-Home, mini-ImageNet/CUB, and DomainNet datasets and demonstrate the efficacy of DAFOS-Net through extensive experimentation.

Multi-task Imitation Learning (MIL) aims to train a policy capable of performing a distribution of tasks based on multi-task expert demonstrations, which is essential for general-purpose robots. Existing MIL algorithms suffer from low data efficiency and poor performance on complex long-horizontal tasks. We develop Multi-task Hierarchical Adversarial Inverse Reinforcement Learning (MH-AIRL) to learn hierarchically-structured multi-task policies, which is more beneficial for compositional tasks with long horizons and has higher expert data efficiency through identifying and transferring reusable basic skills across tasks. To realize this, MH-AIRL effectively synthesizes context-based multi-task learning, AIRL (an IL approach), and hierarchical policy learning. Further, MH-AIRL can be adopted to demonstrations without the task or skill annotations (i.e., state-action pairs only) which are more accessible in practice. Theoretical justifications are provided for each module of MH-AIRL, and evaluations on challenging multi-task settings demonstrate superior performance and transferability of the multi-task policies learned with MH-AIRL as compared to SOTA MIL baselines.

Deep Q-learning based algorithms have been applied successfully in many decision making problems, while their theoretical foundations are not as well understood. In this paper, we study a Fitted Q-Iteration with two-layer ReLU neural network parameterization, and find the sample complexity guarantees for the algorithm. Our approach estimates the Q-function in each iteration using a convex optimization problem. We show that this approach achieves a sample complexity of $\tilde{\mathcal{O}}(1/\epsilon^{2})$, which is order-optimal. This result holds for a countable state-spaces and does not require any assumptions such as a linear or low rank structure on the MDP.

We investigate the problem of stochastic, combinatorial multi-armed bandits where the learner only has access to bandit feedback and the reward function can be non-linear. We provide a general framework for adapting discrete offline approximation algorithms into sublinear $\alpha$-regret methods that only require bandit feedback, achieving $\mathcal{O}\left(T^\frac{2}{3}\log(T)^\frac{1}{3}\right)$ expected cumulative $\alpha$-regret dependence on the horizon $T$. The framework only requires the offline algorithms to be robust to small errors in function evaluation. The adaptation procedure does not even require explicit knowledge of the offline approximation algorithm — the offline algorithm can be used as black box subroutine. To demonstrate the utility of the proposed framework, the proposed framework is applied to multiple problems in submodular maximization, adapting approximation algorithms for cardinality and for knapsack constraints. The new CMAB algorithms for knapsack constraints outperform a full-bandit method developed for the adversarial setting in experiments with real-world data.

Hierarchical Imitation Learning (HIL) has been proposed to recover highly-complex behaviors in long-horizon tasks from expert demonstrations by modeling the task hierarchy with the option framework. Existing methods either overlook the causal relationship between the subtask and its corresponding policy or cannot learn the policy in an end-to-end fashion, which leads to suboptimality. In this work, we develop a novel HIL algorithm based on Adversarial Inverse Reinforcement Learning and adapt it with the Expectation-Maximization algorithm in order to directly recover a hierarchical policy from the unannotated demonstrations. Further, we introduce a directed information term to the objective function to enhance the causality and propose a Variational Autoencoder framework for learning with our objectives in an end-to-end fashion. Theoretical justifications and evaluations on challenging robotic control tasks are provided to show the superiority of our algorithm. The codes are available at https://github.com/LucasCJYSDL/HierAIRL.

Recently, quantum machine learning has been ap-plied to stochastic-based modelling, promising that the inherent uncertainty in quantum computing will be a significant advan-tage, driving neuromorphic computing research to new heights. Spiking Neural Networks (SNNs) and their neuromorphic are gaining popularity due to their inherent ability to process spatial and temporal data. However, learning the interconnection weights is daunting due to the inherent stochastic characteristics of neuron signals and the inherent non-differentiable spike events in classical SNN. This paper introduces a supervised Deep Spiking Quantum Neural Network (DSQ-Net) using a hybrid quantum- classical architecture having the merits of amplitude encoding in a dressed quantum layer. A novel attempt has been made to obviate the challenges in training a classical deep SNN, assisted by a Variational Quantum Circuit (VQC) in the proposed hy-brid quantum-classical framework. The DSQ-Net has undergone thorough validation and benchmarking procedures using the PennyLane Quantum Simulator and the limited volume real IBM Quantum hardware. The experiments have been conducted on images from the MNIST, FashionMNIST, KMNIST, and CIFAR-I0 datasets. Classification accuracy has been reported in the high nineties for unseen noisy test images using the proposed DSQ-Net model on the quantum simulator. It outper-forms its classical counterpart (Deep Spiking Neural Networks), shallow Random Quantum Neural Networks (RQNN), Quantum Superposition-inspired Spiking Neural Networks (SQIN), ResNet- 18, and AlexNet. The PyTorch implementation of DSQ-Net is made available on Github11https://anonymous.4open.science/r/DSQ-Net-037E,

Learning-based approaches have shown their great potential to adapt themselves to various environments (e.g., PCC and Sprout). Unfortunately, they do not consistently achieve superior QoS across different network conditions and configurations in mobile networks. Furthermore, although they can offer multiple application objectives by adjusting a preference weight vector, it is challenging for users to accurately express an application objective with a weight vector. In this work, we argue that, if configured correctly, the delay-based TCP scheme can outperform learned ones, and allow users to directly specify their objectives. To this end, we propose Post-QoS Analysis (PQSA), a data-driven framework that trains the key QoS-impacting parameters of the scheme to capture the statistical correlations between QoS objectives, network conditions, and configurations, thereby determining the optimal parameter-set that meets the user-defined QoS objective under different network conditions and configurations. To support this, we enhance conventional delay-based TCP design to develop a Generalized TCP-like Rate controller (GR) by exporting three key parameters. Extensive evaluations show that PQSA-optimized GR outperforms existing schemes in different scenarios consistently, and enables service providers to control the QoS flexibly.

Fueled by the rapid advances in high-speed mobile networks, live video streaming has seen explosive growth in recent years and many DASH-based bitrate adaptive streaming algorithms were specifically proposed for low-latency video delivery. However, our investigations revealed that these algorithms are susceptible to network condition changes due to the use of solo universal adaptation logics, resulting the playback latency that has substantial variations across highly-fluctuating network environments and fails to meet the service quality requirement all the time. To tackle this challenge, this paper proposes Stateful Live Video Streaming (SLVS), which is a novel learning approach that learns the various network features and optimizes the adaptation logic separately for different network conditions, then dynamically tunes the logic at runtime, so that bitrate decision can better match the changing networks. Extensive evaluations show that SLVS can control playback latency down to 1s while improving Quality-of-Experience (QoE) by 17.7% to 31.8%. Moreover, it has strong robustness to maintain near-second latency over highly-fluctuating networks as well as long-period of video viewing.

Learning rich skills under the option framework without supervision of external rewards is at the frontier of reinforcement learning research. Existing works mainly fall into two distinctive categories: variational option discovery that maximizes the diversity of the options through a mutual information loss (while ignoring coverage) and Laplacian-based methods that focus on improving the coverage of options by increasing connectivity of the state space (while ignoring diversity). In this paper, we show that diversity and coverage in unsupervised option discovery can indeed be unified under the same mathematical framework. To be specific, we explicitly quantify the diversity and coverage of the learned options through a novel use of Determinantal Point Process (DPP) and optimize these objectives to discover options with both superior diversity and coverage. Our proposed algorithm, ODPP, has undergone extensive evaluation on challenging tasks created with Mujoco and Atari. The results demonstrate that our algorithm outperforms state-of-the-art baselines in both diversity- and coverage-driven categories.

Federated reinforcement learning (FedRL) enables agents to collaboratively train a global policy without sharing their individual data. However, high communication overhead remains a critical bottleneck, particularly for natural policy gradient (NPG) methods, which are second-order. To address this issue, we propose the FedNPG-ADMM framework, which leverages the alternating direction method of multipliers (ADMM) to approximate global NPG directions efficiently. We theoretically demonstrate that using ADMM-based gradient updates reduces communication complexity from $\mathcal{O}({d^{2}})$ to $\mathcal{O}({d})$ at each iteration, where $d$ is the number of model parameters. Furthermore, we show that achieving an $\epsilon$-error stationary convergence requires $\mathcal{O}(\frac{1}{(1-\gamma)^{2}{\epsilon}})$ iterations for discount factor $\gamma$, demonstrating that FedNPG-ADMM maintains the same convergence rate as standard FedNPG. Through evaluation of the proposed algorithms in MuJoCo environments, we demonstrate that FedNPG-ADMM maintains the reward performance of standard FedNPG, and that its convergence rate improves when the number of federated agents increases.

In this paper, we prove state-of-the-art Bayesian regret bounds for Thompson Sampling in reinforcement learning in a multitude of settings. We present a refined analysis of the information ratio, and show an upper bound of order $\widetilde{O}(H\sqrt{d_{l_1}T})$ in the time inhomogeneous reinforcement learning problem where $H$ is the episode length and $d_{l_1}$ is the Kolmogorov $l_1-$dimension of the space of environments. We then find concrete bounds of $d_{l_1}$ in a variety of settings, such as tabular, linear and finite mixtures, and discuss how our results improve the state-of-the-art.

This paper presents a unified approach for maximizing continuous DR-submodular functions that encompasses a range of settings and oracle access types. Our approach includes a Frank-Wolfe type offline algorithm for both monotone and non-monotone functions, with different restrictions on the general convex set. We consider settings where the oracle provides access to either the gradient of the function or only the function value, and where the oracle access is either deterministic or stochastic. We determine the number of required oracle accesses in all cases. Our approach gives new/improved results for nine out of the sixteen considered cases, avoids computationally expensive projections in three cases, with the proposed framework matching performance of state-of-the-art approaches in the remaining four cases. Notably, our approach for the stochastic function value-based oracle enables the first regret bounds with bandit feedback for stochastic DR-submodular functions.

Finding optimal policies which maximize long term rewards of Markov Decision Processes requires the use of dynamic programming and backward induction to solve the Bellman optimality equation. However, many real-world problems require optimization of an objective that is non-linear in cumulative rewards for which dynamic programming cannot be applied directly. For example, in a resource allocation problem, one of the objectives is to maximize long-term fairness among the users. We notice that when an agent aim to optimize some function of the sum of rewards is considered, the problem loses its Markov nature. This paper addresses and formalizes the problem of optimizing a non-linear function of the long term average of rewards. We propose model-based and model-free algorithms to learn the policy, where the model-based policy is shown to achieve a regret of $\Tilde{O}\left(LKDS\sqrt{\frac{A}{T}}\right)$ for $K$ objectives combined with a concave $L$-Lipschitz function. Further, using the fairness in cellular base-station scheduling, and queueing system scheduling as examples, the proposed algorithm is shown to significantly outperform the conventional RL approaches.

In the optimization of dynamic systems, the variables typically have constraints. Such problems can be modeled as a Constrained Markov Decision Process (CMDP). This paper considers the peak Constrained Markov Decision Process (PCMDP), where the agent chooses the policy to maximize total reward in the finite horizon as well as satisfy constraints at each epoch with probability 1. We propose a model-free algorithm that converts PCMDP problem to an unconstrained problem and a Q-learning based approach is applied. We define the concept of probably approximately correct (PAC) to the proposed PCMDP problem. The proposed algorithm is proved to achieve an $(\epsilon,p)$-PAC policy when the episode $K\geq\Omega(\frac{I^2H^6SA\ell}{\epsilon^2})$, where $S$ and $A$ are the number of states and actions, respectively. $H$ is the number of epochs per episode. $I$ is the number of constraint functions, and $\ell=\log(\frac{SAT}{p})$. We note that this is the first result on PAC kind of analysis for PCMDP with peak constraints, where the transition dynamics are not known apriori. We demonstrate the proposed algorithm on an energy harvesting problem and a single machine scheduling problem, where it performs close to the theoretical upper bound of the studied optimization problem.

The proliferation of data-intensive mobile applications is causing latency to become an issue in mobile edge computing (MEC) systems. In this work, we propose a novel methodology that optimizes communication, computation, and caching configurations in MEC to minimize the mean latency experienced by mobile devices. Transmission and computation processes are modeled using M/G/1 queues to account for service rates and warm-up times. Our caching scheme includes time variables for each file at each edge server in determining when to discard files from storage. We theoretically analyze the latency experienced by mobile devices due to communication, computation, and caching, showing how MEC system latency depends on the offloading decisions of mobile devices, bandwidth and CPU resources, and expiration times of files in the storage of edge servers. Our method for solving the latency minimization problem consists of two main components: iNner cOnVex Approximation (NOVA) to deal with non-convexity in the optimization, and an online algorithm for preventing cache storage violations as new tasks arrive and are serviced by the MEC system. Simulation results show that our algorithm outperforms several baselines in minimizing latency, and verify the benefit of including different resource allocation variables in our optimization.

Mobile video streaming is now ubiquitous among mobile users. This work investigates a less studied and yet significant problem in mobile video streaming – data wastage, i.e., some downloaded video data may not be played back but discarded by video players due to early departure or video skip, thus the bandwidth consumed in transferring them is wasted. Our measurements show that data wastage is significant in practice, e.g., 25.2 percent∼51.7 percent of video data downloaded are in fact wasted. Moreover, substantial data wastage exists not only in current commercial streaming platforms, but also in state-of-the-art adaptive streaming systems proposed in the literature. This work develops a new post-streaming wastage analysis (PSWA) framework to tackle this problem by converting existing adaptive streaming algorithms into data wastage aware versions. PSWA enables the streaming vendors to explicitly control the tradeoff between data wastage and quality-of-experience (QoE). Extensive evaluations show that PSWA can reduce data wastage significantly (e.g., 80 percent) without any adverse impact on QoE. Moreover, it has strong robustness to perform consistently across a wide range of networks. PSWA can be readily implemented into current streaming platforms, and thus offers a practical solution to data wastage for mobile streaming services.

Video streaming has grown tremendously in recent years and it is now one of the main applications on the Internet. Due to the networks' inherent bandwidth fluctuations, various rate-adaptive streaming algorithms have been developed to compensate for such fluctuations to improve Quality-of-Experience (QoE). However, in practice, the preference for QoE typically differs significantly across different viewers and there is no systematic way so far to comprehensively incorporate different sets of conflicting QoE objectives into the algorithm design. Thus, it is not surprising that the QoE performance achieved by the existing algorithms is in fact far from optimal. This work aims at attacking the heart of the problem by developing a novel framework called Post Streaming Quality Analysis (PSQA) that can maximize the QoE under any preference through automatically tuning the adaptation logic of the streaming algorithms. Evaluation results show that the QoE achieved by PSQA is substantially better than the existing approaches and in some scenarios even close to optimal. Moreover, PSQA can be readily implemented into real streaming platforms, offering a practical and reliable solution for high-performance streaming services.

We propose cooperative edge-assisted dynamic federated learning (CE-FL).CE-FLintroduces a distributed machine learning (ML) architecture, where data collection is carried out at the end devices, while the model training is conducted cooperatively at the end devices and the edge servers, enabled via data offloading from the end devices to the edge servers through base stations.CE-FLalso introduces floating aggregation point, where the local models generated at the devices and the servers are aggregated at an edge server, which varies from one model training round to another to cope with the network evolution in terms of data distribution and users’ mobility.CE-FLconsiders the heterogeneity of network elements in terms of communication/computation models and the proximity to one another.CE-FLfurther presumes a dynamic environment with online variation of data at the network devices which causes a drift at the ML model performance. We model the processes taken duringCE-FL, and conduct analytical convergence analysis of its ML model training. We then formulate network-awareCE-FLwhich aims to adaptively optimize all the network elements via tuning their contribution to the learning process, which turns out to be a non-convex mixed integer problem. Motivated by the large scale of the system, we propose a distributed optimization solver to break down the computation of the solution across the network elements. We finally demonstrate the effectiveness of our framework with the data collected from a real-world testbed.

Blockchains have proven to provide a high level of performance in terms of security and reliability for various applications like cryptocurrencies and Internet-of-Things (IoT). Prism is a recent blockchain algorithm that achieves the physical limit on throughput and latency without compromising security. In recent days, reinforcement learning approaches are investigated in traditional blockchains, to improve performance. In this work, we apply Deep Reinforcement Learning (DRL) to one of the promising blockchain protocols, Prism, to optimize its performance. We propose a Deep Reinforcement Learning-based Prism Blockchain (DRLPB) scheme which dynamically optimizes the parameters of the Prism blockchain and helps in achieving a better performance. In DRLPB, we apply two widely used DRL algorithms, Dueling Deep Q Networks (DDQN) and Proximal Policy Optimization (PPO). This work presents a novel approach to applying DDQN and PPO to a blockchain protocol and comparing the performance. The DRLPB scheme adapts the Prism blockchain parameters to enhance the number of votes upto 84% more than Prism, while still preserving the security and latency performance guarantees of Prism.

Fueled by the emerging short video applications (e.g., TikTok), streaming short-form videos nowadays is ubiquitous among mobile users. During the viewing, one common action is to scroll the screen to switch videos, which is a handy operation for the viewers to quickly search for content of interest. However, our empirical measurements reveal that frequent video switching can result in nearly half of the mobile data quota being used for transferring the video data that is never watched. This problem is called data loss in this work. Given the immense cost of the network infrastructure, such a high proportion of data loss is financially tremendous to both mobile users and streaming vendors. To tackle the problem, this study proposes a novel system called Data Usage Aware Short Video Streaming (DUASVS), where a new Integrated Learning is used to capture the characters of past network conditions and then trains intelligent adaptation models to reduce data loss and save data usage. Extensive evaluations show that DUASVS is able to save 70.7%∼83.2% of mobile data usage without incurring any QoE degradation. Moreover, the system exhibits strong robustness, performing consistently over a wide range of network environments as well as video streaming sessions.

Reinforcement learning is widely used in applications where one needs to perform sequential decisions while interacting with the environment. The problem becomes more challenging when the decision requirement includes satisfying some safety constraints. The problem is mathematically formulated as constrained Markov decision process (CMDP). In the literature, various algorithms are available to solve CMDP problems in a model-free manner to achieve epsilon-optimal cumulative reward with epsilon feasible policies. An epsilon-feasible policy implies that it suffers from constraint violation. An important question here is whether we can achieve epsilon-optimal cumulative reward with zero constraint violations or not. To achieve that, we advocate the use of a randomized primal-dual approach to solve the CMDP problems and propose a conservative stochastic primal-dual algorithm (CSPDA) which is shown to exhibit O(1/epsilon^2) sample complexity to achieve epsilon-optimal cumulative reward with zero constraint violations. In the prior works, the best available sample complexity for the epsilon-optimal policy with zero constraint violation is O(1/epsilon^5). Hence, the proposed algorithm provides a significant improvement compared to the state of the art.

Newton-type methods are popular in federated learning due to their fast convergence. Still, they suffer from two main issues, namely: low communication efficiency and low privacy due to the requirement of sending Hessian information from clients to parameter server (PS). In this work, we introduced a novel framework called FedNew in which there is no need to transmit Hessian information from clients to PS, hence resolving the bottleneck to improve communication efficiency. In addition, FedNew hides the gradient information and results in a privacy-preserving approach compared to the existing state-of-the-art. The core novel idea in FedNew is to introduce a two level framework, and alternate between updating the inverse Hessian-gradient product using only one alternating direction method of multipliers (ADMM) step and then performing the global model update using Newton’s method. Though only one ADMM pass is used to approximate the inverse Hessian-gradient product at each iteration, we develop a novel theoretical approach to show the converging behavior of FedNew for convex problems. Additionally, a significant reduction in communication overhead is achieved by utilizing stochastic quantization. Numerical results using real datasets show the superiority of FedNew compared to existing methods in terms of communication costs.

Covering option discovery has been developed to improve the exploration of RL in single-agent scenarios with sparse reward signals, through connecting the most distant states in the embedding space provided by the Fiedler vector of the state transition graph. Given that joint state space grows exponentially with the number of agents in multi-agent systems, existing researches still relying on single-agent option discovery either become prohibitive or fail to directly discover joint options that improve the connectivity of the joint state space. In this paper, we show how to directly compute multi-agent options with collaborative exploratory behaviors while still enjoying the ease of decomposition. Our key idea is to approximate the joint state space as a Kronecker graph, based on which we can directly estimate its Fiedler vector using the Laplacian spectrum of individual agents' transition graphs. Further, considering that directly computing the Laplacian spectrum is intractable for tasks with infinite-scale state spaces, we further propose a deep learning extension of our method by estimating eigenfunctions through NN-based representation learning techniques. The evaluation on multi-agent tasks built with simulators like Mujoco, shows that the proposed algorithm can successfully identify multi-agent options, and significantly outperforms the state-of-the-art. Codes are available at: https://github.itap.purdue.edu/Clan-labs/ScalableMAODvia_KP.

Multi-agent reinforcement learning (MARL) has witnessed significant progress with the development of value function factorization methods. It allows optimizing a joint action-value function through the maximization of factorized per-agent utilities. In this paper, we show that in partially observable MARL problems, an agent's ordering over its own actions could impose concurrent constraints (across different states) on the representable function class, causing significant estimation errors during training. We tackle this limitation and propose PAC, a new framework leveraging Assistive information generated from Counterfactual Predictions of optimal joint action selection, which enable explicit assistance to value function factorization through a novel counterfactual loss. A variational inference-based information encoding method is developed to collect and encode the counterfactual predictions from an estimated baseline. To enable decentralized execution, we also derive factorized per-agent policies inspired by a maximum-entropy MARL framework. We evaluate the proposed PAC on multi-agent predator-prey and a set of StarCraft II micromanagement tasks. Empirical results demonstrate improved results of PAC over state-of-the-art value-based and policy-based multi-agent reinforcement learning algorithms on all benchmarks.

We consider the problem of constrained Markov Decision Process (CMDP) where an agent interacts with an ergodic Markov Decision Process. At every interaction, the agent obtains a reward and incurs $K$ costs. The agent aims to maximize the long-term average reward while simultaneously keeping the $K$ long-term average costs lower than a certain threshold. In this paper, we propose \NAM, a posterior sampling based algorithm using which the agent can learn optimal policies to interact with the CMDP. We show that with the assumption of slackness, characterized by $\kappa$, the optimization problem is feasible for the sampled MDPs. Further, for MDP with $S$ states, $A$ actions, and mixing time $T_M$, we prove that following \NAM{} algorithm, the agent can bound the regret of not accumulating rewards from an optimal policy by $\Tilde{O}(T_MS\sqrt{AT})$. Further, we show that the violations for any of the $K$ constraints is also bounded by $\Tilde{O}(T_MS\sqrt{AT})$. To the best of our knowledge, this is the first work that obtains a $\Tilde{O}(\sqrt{T})$ regret bounds for ergodic MDPs with long-term average constraints using a posterior sampling method.

Collusion in a competitive multi-agent game occurs when two or more agents co-operate covertly to the disadvantage of others. Most competitive multi-agent games do not allow players to share information and explicitly prohibit collusion. In this paper, we present a novel way of detecting collusion using a domain-independent information-theoretic approach. Specifically, we show that the use of mutual information between actions of the agents provides a good indication of collusive behavior. Our experiments show that our method can detect varying levels of collusion in repeated simultaneous games like iterated Rock Paper Scissors. We further extend the detection to partially observable sequential games like poker and show the effectiveness of our methodology.

Mean-Field Control (MFC) is a powerful tool to solve Multi-Agent Reinforcement Learning (MARL) problems. Recent studies have shown that MFC can well-approximate MARL when the population size is large and the agents are exchangeable. Unfortunately, the presumption of exchangeability implies that all agents uniformly interact with one another which is not true in many practical scenarios. In this article, we relax the assumption of exchangeability and model the interaction between agents via an arbitrary doubly stochastic matrix. As a result, in our framework, the mean-field ‘seen’ by different agents are different. We prove that, if the reward of each agent is an affine function of the mean-field seen by that agent, then one can approximate such a non-uniform MARL problem via its associated MFC problem within an error of $e=\mathcal{O}(\frac{1}{\sqrt{N}}[\sqrt{|\mathcal{X}|} + \sqrt{|\mathcal{U}|}])$ where $N$ is the population size and $|\mathcal{X}|$, $|\mathcal{U}|$ are the sizes of state and action spaces respectively. Finally, we develop a Natural Policy Gradient (NPG) algorithm that can provide a solution to the non-uniform MARL with an error $\mathcal{O}(\max\{e,\epsilon\})$ and a sample complexity of $\mathcal{O}(\epsilon^{-3})$ for any $\epsilon >0$.

We investigate the problem of combinatorial multi-armed bandits with stochastic submodular (in expectation) rewards and full-bandit feedback, where no extra information other than the reward of selected action at each time step $t$ is observed. We propose a simple algorithm, Explore-Then-Commit Greedy (ETCG) and prove that it achieves a $(1-1/e)$-regret upper bound of $\mathcal{O}(n^\frac{1}{3}k^\frac{4}{3}T^\frac{2}{3}\log(T)^\frac{1}{2})$ for a horizon $T$, number of base elements $n$, and cardinality constraint $k$. We also show in experiments with synthetic and real-world data that the ETCG empirically outperforms other full-bandit methods.

Many engineering problems have multiple objectives, and the overall aim is to optimize a non-linear function of these objectives. In this paper, we formulate the problem of maximizing a non-linear concave function of multiple long-term objectives. A policy-gradient based model-free algorithm is proposed for the problem. To compute an estimate of the gradient, an asymptotically biased estimator is proposed. The proposed algorithm is shown to achieve convergence to within an ε of the global optima after sampling O(M4 σ2/(1-γ)8ε4) trajectories where γ is the discount factor and M is the number of the agents, thus achieving the same dependence on ε as the policy gradient algorithm for the standard reinforcement learning.

We consider the problem where $N$ agents collaboratively interact with an instance of a stochastic $K$ arm bandit problem for $K \gg N$. The agents aim to simultaneously minimize the cumulative regret over all the agents for a total of $T$ time steps, the number of communication rounds, and the number of bits in each communication round. We present Limited Communication Collaboration - Upper Confidence Bound (LCC-UCB), a doubling-epoch based algorithm where each agent communicates only after the end of the epoch and shares the index of the best arm it knows. With our algorithm, LCC-UCB, each agent enjoys a regret of $\tilde{O}\left(\sqrt{({K/N}+ N)T}\right)$, communicates for $O(\log T)$ steps and broadcasts $O(\log K)$ bits in each communication step. We extend the work to sparse graphs with maximum degree $K_G$ and diameter $D$ to propose LCC-UCB-GRAPH which enjoys a regret bound of $\tilde{O}\left(D\sqrt{(K/N+ K_G)DT}\right)$. Finally, we empirically show that the LCC-UCB and the LCC-UCB-GRAPH algorithms perform well and outperform strategies that communicate through a central node.

Mean field control (MFC) is an effective way to mitigate the curse of dimensionality of cooperative multi-agent reinforcement learning (MARL) problems. This work considers a collection of $N_{\mathrm{pop}}$ heterogeneous agents that can be segregated into $K$ classes such that the $k$-th class contains $N_k$ homogeneous agents. We aim to prove approximation guarantees of the MARL problem for this heterogeneous system by its corresponding MFC problem. We consider three scenarios where the reward and transition dynamics of all agents are respectively taken to be functions of $(1)$ joint state and action distributions across all classes, $(2)$ individual distributions of each class, and $(3)$ marginal distributions of the entire population. We show that, in these cases, the $K$-class MARL problem can be approximated by MFC with errors given as $e_1=\mathcal{O}(\frac{\sqrt{|\mathcal{X}|}+\sqrt{|\mathcal{U}|}}{N_{\mathrm{pop}}}\sum_{k}\sqrt{N_k})$, $e_2=\mathcal{O}(\left[\sqrt{|\mathcal{X}|}+\sqrt{|\mathcal{U}|}\right]\sum_{k}\frac{1}{\sqrt{N_k}})$ and $e_3=\mathcal{O}\left(\left[\sqrt{|\mathcal{X}|}+\sqrt{|\mathcal{U}|}\right]\left[\frac{A}{N_{\mathrm{pop}}}\sum_{k\in[K]}\sqrt{N_k}+\frac{B}{\sqrt{N_{\mathrm{pop}}}}\right]\right)$, respectively, where $A, B$ are some constants and $|\mathcal{X}|,|\mathcal{U}|$ are the sizes of state and action spaces of each agent. Finally, we design a Natural Policy Gradient (NPG) based algorithm that, in the three cases stated above, can converge to an optimal MARL policy within $\mathcal{O}(e_j)$ error with a sample complexity of $\mathcal{O}(e_j^{-3})$, $j\in\{1,2,3\}$, respectively.

Safety practitioners widely use the lifting index (LI) to determine workers’ lifting risk but are hampered by the difficulties of estimating the lifting load without intervention or intrusive sensors. This study proposes a computer vision method for estimating the LI across varying lifting loads. The proposed method can also predict the Brog rating of perceived exertion (RPE), a measure associated with the lifting load. A controlled lifting experiment was conducted to demonstrate the approach. Thirty participants performed 2176 lifting tasks at three LI levels. These levels were controlled by varying the lifting load and fixing other task variables (e.g., the lifting distance). The proposed method combined the pose estimation (OpenPose) and the optical flow estimation (SelFlow) techniques for extracting the participants’ body motion and posture features; a facial expression recognition algorithm (OpenFace) built upon the facial action unit coding system (FACS) was used to extract the participants’ facial features. The extracted features were combined and used to develop prediction models. The best-performing model was an integration of the 1-D convolutional neural network and the long short-term memory network. It achieved an area under curve of 0.890 in classifying the LI and a root mean square of 2.264 in predicting the participants’ RPE. Critical indicators were identified by investigating the contribution of the features through interpretable machine learning techniques. In summary, this study demonstrates a nonintrusive method for lifting risk assessment and discovers behavioral indicators that predict changes in the LI and RPE due to varying loads.

In this article, we present a novel 3-D descriptor, improved dexel representation (IDR), which assists to input holistic information from an engineering computer-aided design (CAD) model to convolutional neural network (CNN) based manufacturing applications. The IDR carries the model’s position, size, and surface information, which not only provides high resolution to small-scale local (machining) features, but also has the potential to reconstruct the original CAD model. Data conversion algorithms between IDR and other CAD models (mesh and NURBS model) are efficient. CNNs with IDR input can largely improve the prediction accuracy compared to other 3-D descriptors, which reaches 98.8% in the modified machining-process-identifier dataset and 100% on the FeatureNet style 3-class dataset. IDR benefits both the manufacturing industry and other CAD-related deep learning applications in engineering fields.

This paper introduces an adaptive model-free deep reinforcement approach that can recognize and adapt to the diurnal patterns in the ride-sharing environment with car-pooling. Deep Reinforcement Learning (RL) suffers from catastrophic forgetting due to being agnostic to the timescale of changes in the distribution of experiences. Although RL algorithms are guaranteed to converge to optimal policies in Markov decision processes (MDPs), this only holds in the presence of static environments. However, this assumption is very restrictive. In many real-world problems like ride-sharing, traffic control, etc., we are dealing with highly dynamic environments, where RL methods yield only sub-optimal decisions. To mitigate this problem in highly dynamic environments, we (1) adopt an online Dirichlet change point detection (ODCP) algorithm to detect the changes in the distribution of experiences, (2) develop a Deep Q Network (DQN) agent that is capable of recognizing diurnal patterns and making informed dispatching decisions according to the changes in the underlying environment. Rather than fixing patterns by time of week, the proposed approach automatically detects that the MDP has changed, and uses the results of the new model. In addition to the adaptation logic in dispatching, this paper also proposes a dynamic, demand aware vehicle-passenger matching and route planning framework that dynamically generates optimal routes for each vehicle based on online demand, vehicle capacities, and locations. Evaluation on New York City Taxi public dataset shows the effectiveness of our approach in improving the fleet utilization, where less than 50% of the fleet are utilized to serve the demand of up to 90% of the requests, while maximizing profits and minimizing idle times.

The ubiquitous growth of mobility-on-demand services for passenger and goods delivery has brought various challenges and opportunities within the realm of transportation systems. As a result, intelligent transportation systems are being developed to maximize operational profitability, user convenience, and environmental sustainability. The growth of last mile deliveries alongside ridesharing calls for an efficient and cohesive system that transports both passengers and goods. Existing methods address this using static routing methods considering neither the demands of requests nor the transfer of goods between vehicles during route planning. In this paper, we present a dynamic and demand aware fleet management framework for combined goods and passenger transportation that is capable of (1) Involving both passengers and drivers in the decision-making process by allowing drivers to negotiate to a mutually suitable price, and passengers to accept/reject, (2) Matching of goods to vehicles, and the multi-hop transfer of goods, (3) Dynamically generating optimal routes for each vehicle considering demand along their paths, based on the insertion cost which then determines the matching, (4) Dispatching idle vehicles to areas of anticipated high passenger and goods demand using Deep Reinforcement Learning (RL), (5) Allowing for distributed inference at each vehicle while collectively optimizing fleet objectives. Our proposed model is deployable independently within each vehicle as this minimizes computational costs associated with the growth of distributed systems and democratizes decision-making to each individual. Simulations on a variety of vehicle types, goods, and passenger utility functions show the effectiveness of our approach as compared to other methods that do not consider combined load transportation or dynamic multi-hop route planning. Our proposed method showed improvements over the next best baseline in various aspects including a 15% increase in fleet utilization and a 20% increase in average vehicle profits.

The growth of autonomous vehicles, ridesharing systems, and self-driving technology will bring a shift in the way ride hailing platforms plan out their services. However, these advances in technology coupled with road congestion, environmental concerns, fuel usage, vehicles emissions, and the high cost of the vehicle usage have brought more attention to better utilize the use of vehicles and their capacities. In this paper, we propose a novel distributed multi-hop ride-sharing (MHRS) algorithm that uses deep reinforcement learning to learn optimal vehicle dispatch and matching decisions by interacting with the external environment. By allowing customers to transfer between vehicles, i.e., ride with one vehicle for some time and then transfer to another one, MHRS helps in attaining 30% lower cost and 20% more efficient utilization of fleets, as compared to the ride-sharing algorithms. This flexibility of multi-hop feature gives a seamless experience to customers and ride-sharing companies, and thus improves ride-sharing services.

Federated learning has generated significant interest, with nearly all works focused on a “star” topology where nodes/devices are each connected to a central server. We migrate away from this architecture and extend it through thenetworkdimension to the case where there are multiple layers of nodes between the end devices and the server. Specifically, we develop multi-stage hybrid federated learning (MH-FL), a hybrid of intra-and inter-layer model learning that considers the network as amulti-layer cluster-based structure.MH-FLconsiders thetopology structuresamong the nodes in the clusters, including local networks formed via device-to-device (D2D) communications, and presumes asemi-decentralized architecturefor federated learning. It orchestrates the devices at different network layers in a collaborative/cooperative manner (i.e., using D2D interactions) to formlocal consensuson the model parameters and combines it with multi-stage parameter relaying between layers of the tree-shaped hierarchy. We derive the upper bound of convergence forMH-FLwith respect to parameters of the network topology (e.g., the spectral radius) and the learning algorithm (e.g., the number of D2D rounds in different clusters). We obtain a set of policies for the D2D rounds at different clusters to guarantee either a finite optimality gap or convergence to the global optimum. We then develop a distributed control algorithm forMH-FLto tune the D2D rounds in each cluster over time to meet specific convergence criteria. Our experiments on real-world datasets verify our analytical results and demonstrate the advantages ofMH-FLin terms of resource utilization metrics.

The demand for real-time cloud applications has seen an unprecedented growth over the past decade. These applications require rapidly data transfer and fast computations. This article considers a scenario where multiple IoT devices update information on the cloud, and request a computation from the cloud at certain times. The time required to complete the request for computation includes the time to wait for computation to start on busy virtual machines, performing the computation, waiting and service in the networking stage for delivering the output to the end user. In this context, the freshness of the information is an important concern and is different from the completion time. This article proposes novel scheduling strategies for both computation and networking stages. Based on these strategies, the age-of-information (AoI) metric and the completion time are characterized. A convex combination of the two metrics is optimized over the scheduling parameters. The problem is shown to be convex and thus can be solved optimally. Moreover, based on the offline policy, an online algorithm for job scheduling is developed. Numerical results demonstrate significant improvement as compared to the considered baselines.

We consider a server connected to several users over a shared finite capacity link. Each user is equipped with a cache. File requests at the users are generated as independent Poisson processes according to a popularity profile from a fixed finite library of files. The server has access to all the files in the library. Users can store parts of the files or full files from the library in their local caches. The server should send missing parts of the files requested by the users. The server attempts to fulfill the pending requests with minimal transmissions exploiting multicasting and coding opportunities among the pending requests. We consider a queue in which requests for the same file from different users is merged and transmitted simultaneously to all the requested users. We study and compare the performance of this queuing system in terms of queuing delays when LRU caches are used and when coded caching schemes proposed in the literature are used. We provide approximate expressions for the mean queuing delay for these models and establish their effectiveness with simulations. We extend the analysis to the case when transmission errors are also taken into account.

We consider the bandit problem of selecting K out of N arms at each time step. The joint reward can be a non-linear function of the rewards of the selected individual arms. The direct use of a multi-armed bandit algorithm requires choosing among all possible combinations, making the action space large. To simplify the problem, existing works on combinatorial bandits typically assume feedback as a linear function of individual rewards. In this paper, we prove the lower bound for top-K subset selection with bandit feedback with possibly correlated rewards. We present a novel algorithm for the combinatorial setting without using individual arm feedback or requiring linearity of the reward function. Additionally, our algorithm works on correlated rewards of individual arms. Our algorithm, aDaptive Accept RejecT (DART), sequentially finds good arms and eliminates bad arms based on confidence bounds. DART is computationally efficient and uses storage linear in N. Further, DART achieves a regret bound of Õ(K√KNT) for a time horizon T, which matches the lower bound in bandit feedback up to a factor of √log 2NT. When applied to the problem of cross-selling optimization and maximizing the mean of individual rewards, the performance of the proposed algorithm surpasses that of state-of-the-art algorithms. We also show that DART significantly outperforms existing methods for both linear and non-linear joint reward environments.

In this paper, we consider the problem of optimization and learning for constrained and multi-objective Markov decision processes, for both discounted rewards and expected average rewards. We formulate the problems as zero-sum games where one player (the agent) solves a Markov decision problem and its opponent solves a bandit optimization problem, which we here call Markov-Bandit games. We extend $Q$-learning to solve Markov-Bandit games and show that our new $Q$-learning algorithms converge to the optimal solutions of the zero-sum Markov-Bandit games, and hence converge to the optimal solutions of the constrained and multi-objective Markov decision problems. We provide numerical examples where we calculate the optimal policies and show by simulations that the algorithm converges to the calculated optimal policies. To the best of our knowledge, this is the first time Q-learning algorithms guarantee convergence to optimal stationary policies for the multi-objective Reinforcement Learning problem with discounted and expected average rewards, respectively.

Many real-world problems like Social Influence Maximization face the dilemma of choosing the best $K$ out of $N$ options at a given time instant. This setup can be modeled as a combinatorial bandit which chooses $K$ out of $N$ arms at each time, with an aim to achieve an efficient trade-off between exploration and exploitation. This is the first work for combinatorial bandits where the feedback received can be a non-linear function of the chosen $K$ arms. The direct use of multi-armed bandit requires choosing among $N$-choose-$K$ options making the state space large. In this paper, we present a novel algorithm which is computationally efficient and the storage is linear in $N$. The proposed algorithm is a divide-and-conquer based strategy, that we call CMAB-SM. Further, the proposed algorithm achieves a \textit{regret bound} of $\tilde O(K^{\frac{1}{2}}N^{\frac{1}{3}}T^{\frac{2}{3}})$ for a time horizon $T$, which is \textit{sub-linear} in all parameters $T$, $N$, and $K$.

We demonstrate the training of Spiking Neural Networks (SNN) in a novel multi-agent Evolutionary Robotics (ER) framework inspired by competitive evolutionary environments in nature. The topology of a SNN along with morphological parameters of the bot it controls in the ER environment is together treated as a phenotype. Rules of the framework select certain bots and their SNNs for reproduction and others for elimination based on their efficacy in capturing food in a competitive environment. While the bots and their SNNs are not explicitly trained to survive or reproduce using loss functions, these drives emerge implicitly as they evolve to hunt food and survive. Their efficiency in capturing food exhibits the evolutionary signature of punctuated equilibrium. We use this signature to compare the performances of two evolutionary inheritance algorithms on the phenotypes, Mutation and Crossover with Mutation, using ensembles of 100 experiments for each algorithm. We find that Crossover with Mutation promotes 40% faster learning in the SNN than mere Mutation with a statistically significant margin.

In this paper, we propose an energy-efficient federated meta-learning framework. The objective is to enable learning a meta-model that can be fine-tuned to a new task with a few number of samples in a distributed setting and at low computation and communication energy consumption. We assume that each task is owned by a separate agent, so a limited number of tasks is used to train a meta-model. Assuming each task was trained offline on the agent's local data, we propose a lightweight algorithm that starts from the local models of all agents, and in a backward manner using projected stochastic gradient ascent (P-SGA) finds a meta-model. The proposed method avoids complex computations such as computing hessian, double looping, and matrix inversion, while achieving high performance at significantly less energy consumption compared to the state-of-the-art methods such as MAML and iMAML on conducted experiments for sinusoid regression and image classification tasks.

Telesurgery can be hindered by high-latency and low-bandwidth communication networks, often found in austere settings. Even delays of less than one second are known to negatively impact surgeries. To tackle the effects of connectivity associated with telerobotic surgeries, we propose the DESERTS framework. DESERTS provides a novel simulator interface where the surgeon can operate directly on a virtualized reality simulation and the activities are mirrored in a remote robot, almost simultaneously. Thus, the surgeon can perform the surgery uninterrupted, while high-level commands are extracted from his motions and are sent to a remote robotic agent. The simulated setup mirrors the remote environment, including an alpha-blended view of the remote scene. The framework abstracts the actions into atomic surgical maneuvers (surgemes) which eliminate the need to transmit compressed video information. This system uses a deep learning based architecture to perform live recognition of the surgemes executed by the operator. The robot then executes the received surgemes, thereby achieving semi-autonomy. The framework’s performance was tested on a peg transfer task. We evaluated the accuracy of the recognition and execution module independently as well as during live execution. Furthermore, we assessed the framework’s performance in the presence of increasing delays. Notably, the system maintained a task success rate of 87% from no-delays to 5 seconds of delay.

In austere environments, teleoperated surgical robots could save the lives of critically injured patients if they can perform complex surgical maneuvers under limited communication bandwidth. The bandwidth requirement is reduced by transferring atomic surgical actions (referred to as “surgemes”) instead of the low-level kinematic information. While such a policy reduces the bandwidth requirement, it requires accurate recognition of the surgemes. In this paper, we demonstrate that transfer learning across surgical tasks can boost the performance of surgeme recognition. This is demonstrated by using a network pre-trained with peg-transfer data from Yumi robot to learn classification on debridement on data from Taurus robot. Using a pre-trained network improves the classification accuracy achieves a classification accuracy of 76% with only 8 sequences in target domain, which is 22.5% better than no-transfer scenario. Additionally, ablations on transfer learning indicate that transfer learning requires 40% less data compared to no-transfer to achieve same classification accuracy. Further, the convergence rate of the transfer learning setup is significantly higher than the no-transfer setup trained only on the target domain.

Physical injuries induced by lifting are commonly reported in the workplace. Early risk detection is essential for reducing lifting injuries but requires trained observers to perform assessments manually. Machine learning and computer vision techniques have been proposed to aid ergonomists in lifting risk assessments. However, these methods may not bring the practitioners into the decision-making process and frequently not interpretable to practitioners. We conducted a user study with a proposed risk assessment system that consists of a prediction module, explanation module, and prototype user interface. The prediction module consists of a logistics regression model capable of distinguishing the injury risk levels induced by different levels of force exertion in common lifting tasks. The logistics regression model makes predictions based on explainable body motion, posture, and facial features extracted through computer vision techniques. The explanation module makes up of explainable AI techniques. Specifically, a surrogate model provides local explanations for presenting how the system makes each prediction to users. The prototype interface presents the system’s predictions and explanations. A usability study shows that the proposed system increases crowd-workers’ and domain scholars’ performance in assessing workers’ injury risks in lifting. Furthermore, the usability study also shows that the proposed system increases their confidence in the assessment tasks when the system’s evaluations agree with their subjective evaluations.

We consider the problem where $M$ agents interact with $M$ identical and independent environments with $S$ states and $A$ actions using reinforcement learning for $T$ rounds. The agents share their data with a central server to minimize their regret. We aim to find an algorithm that allows the agents to minimize the regret with infrequent communication rounds. We provide dist-UCRL which runs at each agent and prove that the total cumulative regret of $M$ agents is upper bounded as $\Tilde{O}(DS\sqrt{MAT})$ for a Markov Decision Process with diameter $D$, number of states $S$, and number of actions $A$. The agents synchronize after their visitations to any state-action pair exceeds a certain threshold. Using this, we obtain a bound of $O\left(MSA\log(MT)\right)$ on the total number of communications rounds. Finally, we evaluate the algorithm against multiple environments and demonstrate that the proposed algorithm performs at par with an always communication version of the UCRL2 algorithm, while with significantly lower communication.

Traffic for internet video streaming has been rapidly increasing and is further expected to increase with the higher definition videos and IoT applications, such as 360 degree videos and augmented virtual reality applications. While efficient management of heterogeneous cloud resources to optimize the quality of experience is important, existing work in this problem space often left out important factors. In this paper, we present a model for describing a today’s representative system architecture for video streaming applications, typically composed of a centralized origin server and several CDN sites. Our model comprehensively considers the following factors: limited caching spaces at the CDN sites, allocation of CDN for a video request, choice of different ports from the CDN, and the central storage and bandwidth allocation. With the model, we focus on minimizing a performance metric, stall duration tail probability (SDTP), and present a novel, yet efficient, algorithm to solve the formulated optimization problem. The theoretical bounds with respect to the SDTP metric are also analyzed and presented. Our extensive simulation results demonstrate that the proposed algorithms can significantly improve the SDTP metric, compared to the baseline strategies. Small-scale video streaming system implementation in a real cloud environment further validates our results.

In this article, we propose a communication-efficient decentralized machine learning (ML) algorithm, coined quantized group ADMM (Q-GADMM). To reduce the number of communication links, every worker in Q-GADMM communicates only with two neighbors, while updating its model via the group alternating direction method of multipliers (GADMM). Moreover, each worker transmits the quantized difference between its current model and its previously quantized model, thereby decreasing the communication payload size. However, due to the lack of centralized entity in decentralized ML, the spatial sparsity and payload compression may incur error propagation, hindering model training convergence. To overcome this, we develop a novel stochastic quantization method to adaptively adjust model quantization levels and their probabilities, while proving the convergence of Q-GADMM for convex objective functions. Furthermore, to demonstrate the feasibility of Q-GADMM for non-convex and stochastic problems, we propose quantized stochastic GADMM (Q-SGADMM) that incorporates deep neural network architectures and stochastic sampling. Simulation results corroborate that Q-GADMM significantly outperforms GADMM in terms of communication efficiency while achieving the same accuracy and convergence speed for a linear regression task. Similarly, for an image classification task using DNN, Q-SGADMM achieves significantly less total communication cost with identical accuracy and convergence speed compared to its counterpart without quantization, i.e., stochastic GADMM (SGADMM).

Significant development of ride-sharing services presents a plethora of opportunities to transform urban mobility by providing personalized and convenient transportation while ensuring the efficiency of large-scale ride pooling. However, a core problem for such services is route planning for each driver to fulfill the dynamically arriving requests while satisfying given constraints. Current models are mostly limited to static routes with only two rides per vehicle (optimally) or three (with heuristics) (Alonso-Moraet al., 2017), at least in the initial allocation while not ascertaining that opposite-direction rides are not grouped together. In this paper, we present a dynamic, demand aware, and pricing-based vehicle-passenger matching and route planning framework that (1) dynamically generates optimal routes for each vehicle based on online demand, pricing associated with each ride, vehicle capacities and locations. This matching algorithm starts greedily and optimizes over time using an insertion operation, (2) involves drivers in the decision-making process by allowing them to propose a different price based on the expected reward for a particular ride as well as the destination locations for future rides, which is influenced by supply-and-demand computed by the Deep Q-network. (3) allows customers to accept or reject rides based on their set of preferences with respect to pricing and delay windows, vehicle type and carpooling preferences. These (1-3) in tandem with each other enforce grouping rides with the most route-intersections together. (4) Based on demand prediction, our approach re-balances idle vehicles by dispatching them to the areas of anticipated high demand using deep Reinforcement Learning (RL). Our framework is validated using millions of trips extracted from the New York City Taxi public dataset; however, we consider different vehicle types and designed customer utility functions to validate the setup and study different settings. Experimental results show the effectiveness of our approach in real-time and large scale settings.

The growth in online goods delivery is causing a dramatic surge in urban vehicle traffic from last-mile deliveries. On the other hand, ride-sharing has been on the rise with the success of ride-sharing platforms and increased research on using autonomous vehicle technologies for routing and matching. The future of urban mobility for passengers and goods relies on leveraging new methods that minimize operational costs and environmental footprints of transportation systems. This article considers combining passenger transportation with goods delivery to improve vehicle-based transportation. We propose FlexPool: a distributed model-free deep reinforcement learning algorithm that jointly serves passengers & goods workloads by learning optimal dispatch policies from its interaction with the environment. The proposed algorithm pools passengers for a ride-sharing service and delivers goods using a multi-hop transit method. These flexibilities decrease the fleet's operational cost and environmental footprint while maintaining service levels for passengers and goods. The dispatching algorithm based on deep reinforcement learning is integrated with an efficient matching algorithm for passengers and goods. Through simulations on a realistic multi-agent urban mobility platform, we demonstrate that FlexPool outperforms other model-free settings in serving the demands from passengers & goods. FlexPool achieves 30% higher fleet utilization and 35% higher fuel efficiency in comparison to (i) model-free approaches where vehicles transport a combination of passengers & goods without the use of multi-hop transit, and (ii) model-free approaches where vehicles exclusively transport either passengers or goods.

Distributed computing systems often need to consider the scheduling problem involving a collection of highly dependent data-processing tasks that must work in concert to achieve mission-critical objectives. This paper considers the unrelated machine scheduling problem for minimizing weighted sum completion time under arbitrary precedence constraints and on heterogeneous machines with different processing speeds. The problem is known to be strongly NP-hard even in the single machine setting. By making use of Queyranne’s constraint set and constructing a novel Linear Programming relaxation for the scheduling problem under arbitrary precedence constraints, our results in this paper advance the state of the art. We develop a 2(1+(m-1)/D)-approximation algorithm (and 2(1+(m-1)/D)+1-approximation) for the scheduling problem with zero release time (and arbitrary release time), where m is the number of servers and D is the task-skewness product. The algorithm can be efficiently computed in polynomial time using the Ellipsoid method and achieves nearly optimal performance in practice as D>O(m) when the number of tasks per job to schedule is sufficiently larger than the number of machines available. Our implementation and evaluation using a heterogeneous testbed and real-world benchmarks confirms significant improvement in weighted sum completion time for dependent computing tasks.

Coflows model a scheduling setting that is commonly found in a variety of applications in distributed and cloud computing. A stochastic coflow task contains a set of parallel flows with randomly distributed sizes. Further, many applications require non-preemptive scheduling of coflow tasks. This article gives an approximation algorithm on the weighted expected completion time for non-preemptive stochastic coflow scheduling. The proposed approach uses a time-indexed linear program relaxation, and uses its solution to come up with a feasible schedule. This algorithm is shown to achieve an approximation ratio of$(2\log {m}{+}1)(1{+}\sqrt {m {\Delta }})(1{+}m\sqrt {{\Delta }}){(1{+}{\Delta })}$for zero-release times, and$2(2\log {m}{+}1)(1{+}\sqrt {m{\Delta }})(1{+}m\sqrt {{\Delta }})(1{+}{\Delta })$for general release times, where${\Delta }$represents the upper bound of squared coefficient of variation of processing times, and${m}$is the number of servers.

Given the unpredictable nature of the nodes in distributed computing systems, some of the tasks can be significantly delayed. Such delayed tasks are called stragglers. Straggler mitigation can be achieved by redundant computation. In maximum distance separable (MDS) redundancy method, a task is divided into$k$subtasks which are encoded to$n$coded subtasks, such that a task is completed if any$k$out of$n$coded subtasks are completed. Two important metrics of interest are task completion time, and server utilization which is the aggregate completed work by all servers in this duration. We consider a proactive straggler mitigation strategy where$n_{0}$out of$n$coded subtasks are started at time 0 while the remaining$n-n_{0}$coded subtasks are launched when$\ell _{0}\le \min \left \{{n_{0},k}\right \}$of the initial ones finish. The coded subtasks are halted when$k$of them finish. For this flexible forking strategy with multiple parameters, we analyze the mean of two performance metrics when the random service completion time at each server is independent and distributed identically (i.i.d.) to a shifted exponential. From this study, we find a tradeoff between the metrics which provides insights into the parameter choices. Experiments on Intel DevCloud illustrate that the shifted exponential distribution adequately captures the random coded subtask completion times, and our derived insights continue to hold.

Live video streaming has seen tremendous growth in the past decade. An important fact in live streaming is that the demand for low playback-latency inherently conflicts with the desire for high QoE. This requires different types of live services to seek different latency-QoE tradeoffs according to their service-requirements. However, our investigations revealed that it is fundamentally difficult for existing streaming algorithms to keep consistent latency in changing network conditions, let alone achieve the service-desired latency-QoE tradeoff. To tackle the challenge, this article develops a novel framework called Flexible Latency Aware Streaming (FLAS) that not only can achieve consistent low latency, but also control the latency-QoE tradeoff flexibly. Specifically, FLAS generates a set of adaptation logics offline, each optimized for a candidate tradeoff point, then selects the most appropriate one to run online. We first show how FLAS can be applied to optimizing the existing algorithms, then developed a novel Genetic Programming approach to fully exploit FLAS's potential. Extensive evaluations show that FLAS can precisely control latency all the way down to 1s and achieve substantially higher QoE than state-of-the-arts. FLAS can be readily implemented into real streaming platforms, offering a practical and reliable solution for live-streaming services.

Amazon EC2 provides two most popular pricing schemes–i) thecostlyon-demand instance where the job is guaranteed to be completed, and ii) thecheapspot instance where a job may be interrupted. We consider a user can select a combination of on-demand and spot instances to finish a task. Thus he needs to find the optimal bidding price for the spot-instance, and the portion of the job to be run on the on-demand instance. We formulate the problem as an optimization problem and seek to find the optimal solution. We consider three bidding strategies: one-time requests with expected guarantee, one-time requests with penalty for incomplete job and violating the deadline, and persistent requests. Even without a penalty on incomplete jobs, the optimization problem turns out to be non-convex. Nevertheless, we show that the portion of the job to be run on the on-demand instance is at most half. If the job has a higher execution time or smaller deadline, the bidding price is higher and vice versa. Additionally, the user never selects the on-demand instance if the execution time is smaller than the deadline. The numerical results illustrate the sensitivity of the effective portfolio to several of the parameters involved in the model. Our empirical analysis on the Amazon EC2 data shows that our strategies can be employed on the real instances, where the expected total cost of the proposed scheme decreases over 45 percent compared to the baseline strategy.

The demand for high network capacity has been rapidly increasing, such as inter-DC WANs. But the transport over the network with high bandwidth and delay cannot fully utilize the bandwidth because of the inevitable packet loss and the flow control bottleneck caused by the out-of-order data blocked in the receive buffer. We further found that a lot of applications over inter-DC WANs are non-real-time, which are insensitive to data arriving sequence. Thus, we design and implement Freeway, a user-space bulk-data network transfer framework, to improve the bandwidth of these non-real-time applications over inter-DC WANs. Experimental results show that Freeway achieves 100% more bandwidth utilization than Linux TCP stack, and significantly reduces memory cost.

In this paper, we propose a communication-efficient decen-tralized machine learning (ML) algorithm, coined quantized group ADMM (Q-GADMM). Every worker in Q-GADMM communicates only with two neighbors, and updates its model via the group alternating direct method of multiplier (GADMM), thereby ensuring fast convergence while reducing the number of communication rounds. Furthermore, each worker quantizes its model updates before transmissions, thereby decreasing the communication payload sizes. We prove that Q-GADMM converges to the optimal solution for convex loss functions, and numerically show that Q-GADMM yields 7x less communication cost while achieving almost the same accuracy and convergence speed compared to GADMM without quantization.

Traffic engineering (TE) in multi-region networks is a challenging problem due to the requirement that each region must independently compute its routing decisions based on local observations, yet with the goal of optimizing global TE objectives. Traditional approaches often lack the agility to adapt to changing traffic patterns and thus may suffer hefty performance loss under highly dynamic traffic demands. In this paper, we propose a data-driven framework for multi-region TE problems, which makes novel use of multi-agent deep reinforcement learning. In particular, we propose two reinforcement learning agents for each region, namely T-agents and O-agents, to control the terminal traffic and outgoing traffic, respectively. These distributed agents collect local link utilization statistics within their regions, optimize local routing decisions, and observe the resulting congestion-related reward. To facilitate these agents for optimizing global TE objectives, we tailor the agent design carefully including input, output, and reward functions. The proposed framework is evaluated extensively using real-world network topologies (e.g., Telstra and Google Cloud) and synthetic traffic patterns (e.g., the Gravity model). Numerical results show that comparing with existing protocols and single-agent learning algorithms, our solution can significantly reduce congestion and achieve nearly-optimal performance with both superior scalability and robustness. Throughout our simulations, over 90% of tests limit congestion within 1.2 times the global optimal solution.

Straggler mitigation can be achieved by redundant computation. In MDS redundancy method, a task is divided into k sub-tasks which are encoded to n coded sub-tasks, such that a task is completed if any k coded sub-tasks are completed. Two important metrics of interest are task completion time, and server utilization cost which is the aggregate completed work by all servers in this duration. We consider a proactive straggler mitigation strategy where n0out of n coded sub-tasks are started at time 0 while the remaining n - n0coded sub-tasks are launched when ℓ0≤ min(n0, k) of the initial ones finish. The coded sub-tasks are halted when k of them finish. For this flexible forking strategy with multiple parameters, we analyze the mean of two performance metrics for the proposed forking strategy when the random service completion time at each server is independent and distributed identically to a shifted exponential. Our analysis demonstrates that the regime of n00= n), and is thus not a regime of interest. For n0≥ k, we find that there is a tradeoff between the two performance metrics and leads to decrease in mean server utilization cost at the expense of mean service completion time and an efficient choice of the parameters is helpful.

A variant of the index coding problem (ICP), the embedded index coding problem (EICP) was introduced in [A. Porter and M. Wootters, "Embedded Index Coding," ITW, Sweden, 2019] which was motivated by its application in distributed computing where every user can act as sender for other users and an algorithm for code construction was reported. The construction depends on the computation of minrank of a matrix, which is computationally intensive. In [A.A. Mahesh, N. S. Karat and B. S. Rajan, "Min-rank of Embedded Index Coding Problems," ISIT, 2020], the authors have provided an explicit code construction for a class of EICP - Consecutive and Symmetric Embedded Index Coding Problem (CS-EICP). We introduce the idea of sub-packetization of the messages in index coding problems to provide a novel code construction for CSEICP in contrast to the scalar linear solutions provided in the prior works. For CS-EICP, the normalized rate, which is defined as the number of bits transmitted by all the users together normalized by the total number of bits of all the messages, for our construction is lesser than the normalized rate achieved by Mahesh et al., for scalar linear codes.

When the data is distributed across multiple servers, lowering the communication cost between the servers (or workers) while solving the distributed learning problem is an important problem and is the focus of this paper. In particular, we propose a fast, and communication-efficient decentralized framework to solve the distributed machine learning (DML) problem. The proposed algorithm, Group Alternating Direction Method of Multipliers (GADMM) is based on the Alternating Direction Method of Multipliers (ADMM) framework. The key novelty in GADMM is that it solves the problem in a decentralized topology where at most half of the workers are competing for the limited communication resources at any given time. Moreover, each worker exchanges the locally trained model only with two neighboring workers, thereby training a global model with a lower amount of communication overhead in each exchange. We prove that GADMM converges to the optimal solution for convex loss functions, and numerically show that it converges faster and more communication-efficient than the state-of-the-art communication-efficient algorithms such as the Lazily Aggregated Gradient (LAG) and dual averaging, in linear and logistic regression tasks on synthetic and real datasets. Furthermore, we propose Dynamic GADMM (D-GADMM), a variant of GADMM, and prove its convergence under the time-varying network topology of the workers.

Coding theoretic techniques have been proposed for synchronous Gradient Descent (GD) on multiple servers to mitigate stragglers. These techniques provide the flexibility that the job is complete when any k out of n servers finish their assigned tasks. The task size on each server is found based on the values of k and n. However, it is assumed that all the n jobs are started when the job is requested. In contrast, we assume a tiered system, where we start with n1≥ k tasks, and on completion of c tasks, we start n2- n1more tasks. The aim is that as long as k servers can execute their tasks, the job gets completed. This paper exploits the flexibility that not all servers are started at the request time to obtain the achievable task sizes on each server. The task sizes are in general lower than starting all n2tasks at the request times thus helping achieve lower task sizes which helps to reduce both the job completion time and the total server utilization.

This paper proposes and evaluates a novel algorithm for streaming video over HTTP. The problem is formulated as a non-convex optimization problem which is constrained by the predicted available bandwidth, chunk deadlines, available video rates, and buffer occupancy. The objective is to optimize a QoE metric that maintains a tradeoff between maximizing the playback rate of every chunk and ensuring fairness among different chunks for the minimum re-buffering time. We propose FastScan, a low complexity algorithm that solves the problem. The online adaptations for dynamic bandwidth environments are proposed with imperfect available bandwidth prediction. The results of experiments driven by variable bit rate (VBR) encoded video, video platform system (dash.js), and cellular bandwidth traces of a public dataset reveal the robustness of the online version of FastScan algorithm and demonstrate its significant performance improvement as compared to the considered state-of-the-art video streaming algorithms. For example, on an experiment conducted over 100 real cellular available bandwidth traces of a public dataset that spans different available bandwidth regimes, our proposed algorithm (FastScan) achieves the minimum re-buffering (stall) time and the maximum average playback rate in every single trace as compared to Bola, Festive, BBA, RB, FastMPC, and Pensieve algorithms.

The low-tubal-rank tensor model has been recently proposed for real-world multidimensional data. In this paper, we study the low-tubal-rank tensor completion problem, i.e., to recover a third-order tensor by observing a subset of its elements selected uniformly at random. We propose a fast iterative algorithm, called Tubal-AltMin, that is inspired by a similar approach for low-rank matrix completion. The unknown low-tubal-rank tensor is represented as the product of two much smaller tensors with the low-tubal-rank property being automatically incorporated, and Tubal-AltMin alternates between estimating those two tensors using tensor least squares minimization. First, we note that tensor least squares minimization is different from its matrix counterpart and nontrivial as the circular convolution operator of the low-tubal-rank tensor model is intertwined with the sub-sampling operator. Secondly, the theoretical performance guarantee is challenging since Tubal-AltMin is iterative and nonconvex. We prove that 1) Tubal-AltMin generates a best rank-r approximate up to any predefined accuracy ε at an exponential rate, and 2) for an n × n × k tensor M with tubal-rank r ≪ n, the required sampling complexity is O((nr2kIIMIIF2log3n)/σ2rk), where σ̅rk is the rk-th singular value of the block diagonal matrix representation of M in the frequency domain, and the computational complexity is O(n2r2k3logn log(n/ε)). Finally, on both synthetic data and real-world video data, evaluation results show that compared with tensor-nuclear norm minimization using alternating direction method of multipliers (TNN-ADMM), Tubal-AltMin-Simple (a simplified implementation of Tubal-AltMin) improves the recovery error by several orders of magnitude. In experiments, Tubal-AltMin-Simple is faster than TNN-ADMM by a factor of 5 for a 200 × 200 × 20 tensor.

Most client hosts are equipped with multiple network interfaces (e.g., WiFi and cellular networks). Simultaneous access of multiple interfaces can significantly improve the users' quality of experience (QoE) in video streaming. An intuitive approach to achieve it is to use Multi-path TCP (MPTCP). However, the deployment of MPTCP, especially with link preference, requires OS kernel update at both the client and server side, and a vast amount of commercial content providers do not support MPTCP. Thus, in this paper, we realize a multi-path video streaming algorithm in the application layer instead, by considering Scalable Video Coding (SVC), where each layer of every chunk can be fetched from only one of the orthogonal paths. We formulate the quality decisions of video chunks subject to the available bandwidth of the different paths, chunk deadlines, and link preferences as an optimization problem. The objective is to to optimize a QoE metric that maintains a tradeoff between maximizing the playback rate of every chunk and ensuring fairness among chunks. The proposed metric prefers to use bandwidth of the links to optimize a concave utility function of the chunk quality. Even though the formulation is a non-convex discrete optimization, we provide a quadratic complexity algorithm which is shown to be optimal in some special cases. We further propose an online algorithm where several challenges including bandwidth prediction errors, are addressed. Extensive emulated experiments in a real testbed with real traces of public dataset reveal the robustness of our scheme and demonstrate its significant performance improvement compared to other multi-path algorithms.

Recent advances in high-speed mobile networks have revealed new bottlenecks in ubiquitous TCP protocol deployed in the Internet. In addition to differentiating non-congestive loss from congestive loss, our experiments revealed two significant performance bottlenecks during the loss recovery phase: flow control bottleneck and application stall, resulting in degradation in QoS performance. To tackle these two problems, we first develop a novel opportunistic retransmission algorithm to eliminate the flow control bottleneck, which enables TCP sender to transmit new packets even if receiver's receiving window is exhausted. Second, application stall can be significantly alleviated by carefully monitoring and tuning the TCP sending buffer growth mechanism. We implemented and modularized the proposed algorithms in the Linux kernel thus they can plug-and-play with the existing TCP loss recovery algorithms easily. We evaluated our proposed algorithms over emulated and real experiments and showed that, compared to existing TCP loss recovery algorithms, the proposed optimization algorithms improve the bandwidth efficiency by up to 133 percent and completely mitigate RTT spikes, i.e., over 50 percent RTT reduction, over the loss recovery phase.

Distributed storage systems are known to be susceptible to long response time, and higher latency leads to a reduction in customers satisfaction. An elegant solution to reduce latency in such systems is through two methods - having redundancy in contents at the storage nodes, and adding a cache close to end-users. Redundancy could be added using an erasure code because of its high resiliency with low storage overhead. It is important to quantify the performance of distributed storage systems in the presence of redundancy and caching, which is the focus of this work. This paper proposes a framework for quantifying and jointly optimizing mean and tail latency in erasure-coded storage systems with edge-caching capabilities. A novel caching policy for caching contents in erasure-coded storage systems, called time-to-live (TTLCache), is proposed. Using TTLCache policy and probabilistic server-selection techniques, bounds for mean latency and latency tail probability (LTP) are characterized. A convex combination of both metrics is optimized over the choices of probabilistic scheduling and TTLCache parameters using an efficient algorithm. In all tested cases, the experimental results show the superiority of our approach as compared to the state of the other algorithms and some competitive baselines. Implementation in a real cloud environment is further used to validate the results.

The performance of large-scale distributed compute systems is adversely impacted by stragglers when the execution time of a job is uncertain. To manage stragglers, we consider a multi-fork approach for job scheduling, where additional parallel servers are added at forking instants. In terms of the forking instants and the number of additional servers, we compute the job completion time and the cost of server utilization when the task processing times are assumed to have a shifted exponential distribution. We use this study to provide insights into the scheduling design of the forking instants and the associated number of additional servers to be started. Numerical results demonstrate orders of magnitude improvement in cost in the regime of low completion times as compared to the prior works.

With the advent of emerging mission-critical applications, sampling information updates and scheduling mobile traffic in a timely manner are very challenging. In addition, maintaining fresh information and low latency communication is important to these applications. To that end, in this paper, we first derive closed form expressions for an upper bound on the latency tail probability (LTP) and the average age of information (AoI) in M/G/1 systems, where shifted exponential service time is considered. Different from the majority of existing work in this domain, our analysis is derived under different update size assumption with different priority levels. Next, we have developed novel policies for sampling and scheduling the information updates over the choice of one of the parallel links, e.g., WiFi and LTE links. Then, a joint minimization of AoI and LTP is formulated and efficient algorithms are provided. Our evaluation results show that our proposed approaches outperform the state-of-the-art algorithms and some competitive baselines.

One of the 5G promises is to provide Ultra Reliable Low Latency Communications (URLLC) which targets an end to end communication latency that is <; 1ms. The very low latency requirement of URLLC entails a lot of work in all networking layers. In this paper, we focus on the physical layer, and in particular, we propose a novel formulation of the massive MIMO uplink detection problem. We introduce an objective function that is a sum of strictly convex and separable functions based on decomposing the received vector into multiple vectors. Each vector represents the contribution of one of the transmitted symbols in the received vector. Proximal Jacobian Alternating Direction Method of Multipliers (PJADMM) is used to solve the new formulated problem in an iterative manner where at every iteration all variables are updated in parallel and in a closed form expression. The proposed algorithm provides a lower complexity and much faster processing time compared to the conventional MMSE detection technique and other iterative-based techniques, especially when the number of single antenna users is close to the number of base station (BS) antennas. This improvement is obtained without any matrix inversion. Simulation results demonstrate the efficacy of the proposed algorithm in reducing detection processing time in the multi-user uplink massive MIMO setting.

In this paper, a method is proposed to overcome the consensus error in an average consensus problem, under a distributed setting and with finite-bit communications between the network agents. Previous works have illustrated that the average consensus problem can be solved under a distributed setting, using the Alternating Direction Method of Multipliers (ADMM) method, in which consensus can be attained by using locally available information along with information from neighboring nodes. This holds true even under finite-bit exchanges between neighbouring nodes, but suffers from consensus errors and cyclic states due to the introduced quantization schemes. This work deals with achieving perfect consensus with finite-bit communications between neighboring nodes. We propose an algorithm which leads to perfect consensus in an asymptotic sense, without the need to increase the per-exchange communication rate of the network.

The two-sender unicast index coding problem consists of two senders collectively having all the demanded messages of a set of receivers, where each receiver demands a unique message. The senders avail the knowledge of the side-information present at all the receivers to reduce the total number of broadcast transmissions. This problem is relevant in many practical communication problems like multi-source satellite communication, multi-user coded cooperative data exchange, and other related problems. In this paper, the two-sender unicast index coding problem is analyzed using three independent single-sender subproblems. Optimal broadcast rate (total number of transmitted bits per message bit as the message length tends to infinity) for all the unsolved instances of a special class of the two-sender unicast index coding problem is provided in terms of those of the three associated subproblems. The optimal broadcast rate established in this work serves as a lower bound for the optimal broadcast rate of any general associated two-sender unicast index coding problem. An achievable broadcast rate (total number of transmitted bits per message bit) with finite length messages for any finite length, is given for a subclass of the two-sender unicast index coding problem by providing a code-construction. This serves as a tighter upper bound when compared to the prior state of art.

In the future, deployable, teleoperated surgical robots can save the lives of critically injured patients in battlefield environments. These robotic systems will need to have autonomous capabilities to take over during communication delays and unexpected environmental conditions during critical phases of the procedure. Understanding and predicting the next surgical actions (referred as “surgemes”) is essential for autonomous surgery. Most approaches for surgeme recognition cannot cope with the high variability associated with austere environments and thereby cannot “transfer” well to field robotics. We propose a methodology that uses compact image representations with kinematic features for surgeme recognition in the DESK dataset. This dataset offers samples for surgical procedures over different robotic platforms with a high variability in the setup. We performed surgeme classification in two setups: 1) No transfer, 2) Transfer from a simulated scenario to two real deployable robots. Then, the results were compared with recognition accuracies using only kinematic data with the same experimental setup. The results show that our approach improves the recognition performance over kinematic data across different domains. The proposed approach produced a transfer accuracy gain up to 20% between the simulated and the real robot, and up to 31% between the simulated robot and a different robot. A transfer accuracy gain was observed for all cases, even those already above 90%.

We consider a wireless system with one server and several users making requests from a fixed library of files. The request process from each user is assumed to be an independent Poisson process. The pending requests at the server are queued in a special queue called multicast queue. In this queue, the requests for the same file are merged. A transmission from the server is received by all the users who have requested the file. The channel from the server to each user experiences block fading. We propose several queuing and service strategies for this system and compare their mean response time. We show that our multicast queue significantly out-performs the usual first-in-first-out (FIFO) queue with no merging. We also propose a power control policy to further improve the performance.

This paper proposes an algorithm to minimize weighted service latency for different classes of tenants (or service classes) in a data center network where erasure-coded files are stored on distributed disks/racks and access requests are scattered across the network. Due to the limited bandwidth available at both top-of-the-rack and aggregation switches, and differentiated service requirements of the tenants, network bandwidth must be apportioned among different intra- and inter-rack data flows for different service classes in line with their traffic statistics. We formulate this problem as weighted queuing and employ a class of probabilistic request scheduling policies to derive a closed-form upper-bound of service latency for erasure-coded storage with arbitrary file access patterns and service time distributions. The result enables us to propose a joint weighted latency (over different service classes) optimization over three entangled “control knobs”: the bandwidth allocation at top-of-the-rack and aggregation switches for different service classes, dynamic scheduling of file requests, and the placement of encoded file chunks (i.e., data locality). The joint optimization is shown to be a mixed-integer problem. We develop an iterative algorithm which decouples and solves the joint optimization as 3 sub-problems, which are either convex or solvable via bipartite matching in polynomial time. The proposed algorithm is prototyped in an open-source, distributed file system, Tahoe, and evaluated on a cloud testbed with 16 separate physical hosts in an OpenStack cluster using Cisco switches. Experiments validate our theoretical latency analysis and show significant latency reduction for diverse file access patterns. The results provide valuable insights on designing low-latency data center networks with erasure coded storage.

The two-sender unicast index coding problem consists of two senders, each having a different set of messages. Some messages may be common to both the senders. Each receiver demands a unique message and has a subset of messages known as its side-information. The senders transmit coded messages by availing the knowledge of the side-information of all the receivers, such that all the receivers are able to decode their demands. The aim is to find the optimal aggregate number of coded transmissions per message length (also called the optimal broadcast rate with finite length messages), and its limiting value as the message length tends to infinity (also called the optimal broadcast rate). In this paper, only linear coding schemes are considered. Optimal linear broadcast rate for any finite message length and optimal linear broadcast rate for a basic class of the two-sender unicast index coding problem are established. Optimal code-constructions are also provided. These results are given in terms of the corresponding results of three independent single-sender sub-problems of the two-sender unicast index coding problem. Proof techniques used to obtain the results for the two-sender problem are shown to be useful in obtaining the results for some classes of the multi-sender unicast index coding problem.

The problem of two-sender unicast index coding consists of two senders and a set of receivers. Each receiver demands a unique message not demanded by any other receiver and has a subset of messages as its side information. Every demanded message is available with at least one of the senders. The senders avail the knowledge of the side information at all the receivers to reduce the total number of transmissions required to satisfy the demands of all the receivers. The objective is to find the minimum total of number of transmissions per message length (known as the optimal broadcast rate with finite length messages) and its limiting value as the message length tends to infinity (called the optimal broadcast rate). Achievable broadcast rates are provided for a class of the two-sender unicast index coding problem based on a special graph coloring technique called two-sender graph coloring. This result illustrates the utility of graph products in the two-sender unicast index coding problem for the first time in the literature. For another class, achievable broadcast rates are provided based on the optimal broadcast rates of three single-sender sub-problems with finite message length. This employs a code construction for the two-sender unicast index coding problem using optimal codes (including non-linear codes) of the sub-problems. Optimal broadcast rates are provided for a special class of the TUICP for which only an upper bound was known prior to this work. The optimal broadcast rates presented in this work also consider non-linear coding schemes at the two senders.

In this paper, we formulate a problem that is a variant of the knapsack problem. Even though the problem is NP-hard in general, we consider a special case of the problem where the problem is in P. For this special case, the proposed algorithm is linear time complexity in the number of bins. The proposed framework is a generalization of the framework that has been used recently in the context of finding rate adaptation algorithms for video streaming.

In this paper, we propose a cooperative multi-user video streaming system, termed GiantClient, for videos encoded using scalable video coding (SVC). The proposed system allows a group of users to watch a video on a single screen. The users, who may have different data plans from different carriers or different levels of energy, can collaborate to fetch the SVC-encoded video at high quality and avoid running into re-buffering. Using SVC, each layer of every chunk of the video can be fetched by only one of the cooperating users. Therefore, we formulate the streaming problem that obtains the quality and the fetching policy decisions as an optimization problem. The objective is to optimize a novel quality-of-experience metric that maintains a tradeoff between maximizing the quality of every chunk and ensuring fairness among all video chunks for the minimum re-buffering time. The problem is constrained with the available bandwidth, the chunk deadlines, and the imposed maximum contribution constraints by users. Moreover, we propose a low-complexity algorithm to solve the proposed optimization problem. A real implementation of the system with real SVC-encoded videos and real bandwidth traces reveal the robustness and performance of the proposed algorithm.

We consider users who may have renewable energy harvesting devices or distributed generators. Such users can behave as consumers or producers (hence, we denote them as prosumers) at different time instances. We consider a tiered market where the grid selects a price function, which reveals price in the real time based on the total demand to the grid. In the real time, a prosumer can buy from another prosumer in an exchange market knowing the price from the grid. The exchange price is set by a platform and can be different for different sellers. A prosumer is a selfish entity, which selects the amount of energy it wants to buy either from the grid or from other prosumers or the amount of excess energy it wants to sell to other prosumers by maximizing its own payoff. However, the strategy and the payoff of a prosumer inherently depend on the strategy of other prosumers as a prosumer can only buy if the other prosumers are willing to sell. We formulate the problem as a coupled constrained game and seek to obtain the generalized Nash equilibrium. We show that the game is a concave potential game and show that there exists a unique generalized Nash equilibrium. We propose a distributed algorithm that converges to the exchange price, which clears the market and achieves the generalized Nash equilibrium. We, finally, show how the grid should select the price function in a day-ahead scenario by computing the estimated demand from the history. Our numerical result shows that the tiered market can reduce the peak load and increase the prosumers' total payoffs.

We investigate the fundamental conditions on the sampling pattern, i.e., locations of the sampled entries, for finite completability of a low-rank tensor given some components of its Tucker rank. In order to find the deterministic necessary and sufficient conditions, we propose an algebraic geometric analysis on the Tucker manifold, which allows us to incorporate multiple rank components in the proposed analysis in contrast with the conventional geometric approaches on the Grassmannian manifold. This analysis characterizes the algebraic independence of a set of polynomials defined based on the sampling pattern, which is closely related to finite completability of the sampled tensor, where finite completability simply means that the number of possible completions of the sampled tensor is finite. Probabilistic conditions are then studied and a lower bound on the sampling probability is given, which guarantees that the proposed deterministic conditions on the sampling patterns for finite completability hold with high probability. Furthermore, using the proposed geometric approach for finite completability, we propose a sufficient condition on the sampling pattern that ensures there exists exactly one completion of the sampled tensor.

Content delivery networks store information distributed across multiple servers, so as to balance the load and avoid unrecoverable losses in case of node or disk failures. Coded caching has been shown to be a useful technique which can reduce peak traffic rates by pre-fetching popular content at the end users and encoding transmissions so that different users can extract different information from the same packet. On one hand, distributed storage limits the capability of combining content from different servers into a single message, causing performance losses in coded caching schemes. But, on the other hand, the inherent redundancy existing in distributed storage systems can be used to improve the performance of those schemes through parallelism. This paper designs coded caching and delivery schemes tailored towards systems where the library is distributed across multiple servers, possibly with some redundancy in the form of maximum distance separable (MDS) erasure codes. Different schemes are proposed based on the capacity of the users’ caches, as well as the number of parity servers. The main focus is on scenarios with one (RAID-4) or two (RAID-6) parity servers, but the paper also includes simple extensions for cases with more than two or no parity servers at all. The proposed schemes are shown to reduce the worst case latency, or equivalently the peak transmission rate from any server, below that of state-of-the-art algorithms.

The success of modern ride-sharing platforms crucially depends on the profit of the ride-sharing fleet operating companies, and how efficiently the resources are managed. Further, ride-sharing allows sharing costs and, hence, reduces the congestion and emission by making better use of vehicle capacities. In this paper, we develop a distributed model-free, DeepPool, that uses deep Q-network (DQN) techniques to learn optimal dispatch policies by interacting with the environment. Further, DeepPool efficiently incorporates travel demand statistics and deep learning models to manage dispatching vehicles for improved ride sharing services. Using real-world dataset of taxi trip records in New York, DeepPool performs better than other strategies, proposed in the literature, that do not consider ride sharing or do not dispatch the vehicles to regions where the future demand is anticipated. Finally, DeepPool can adapt rapidly to dynamic environments since it is implemented in a distributed manner in which each vehicle solves its own DQN individually without coordination.

Distributed storage systems are known to be susceptible to long tails in response time. In modern online storage systems such as Bing, Facebook, and Amazon, the long tails of the service latency are of particular concern, with 99.9th percentile response times being orders of magnitude worse than the mean. As erasure codes emerge as a popular technique to achieve high data reliability in distributed storage while attaining space efficiency, taming tail latency still remains an open problem due to the lack of mathematical models for analyzing such systems. To this end, we propose a framework for quantifying and optimizing tail latency in erasure-coded storage systems. In particular, we derive upper bounds on tail latency in closed-form for arbitrary service time distribution and heterogeneous files. Based on the model, we formulate an optimization problem to jointly minimize weighted latency tail probability of all files over the placement of files on the servers, and the choice of servers to access the requested files. The non-convex problem is solved using an efficient, alternating optimization algorithm. Further, we mathematically quantify, in closed form, the tail index, i.e., the exponent at which latency tail probability diminishes to zero, of the service latency for arbitrary erasure-coded storage, by characterizing the asymptotic behavior of latency distribution tails. We further show that probabilistic scheduling-based algorithms are (asymptotically) optimal since they are able to achieve the exact tail index. Evaluation results show significant reduction of tail latency for erasure-coded storage systems with realistic workload. Based on the offline algorithm, an online version is developed and its superiority over the state-of-the-art algorithms, e.g., join-shortest-queue (JSQ), power-of-d [Pof(d))], least-load [LL(d)], is shown. Finally, a cloud storage system is implemented in a real cloud environment to show the superiority of our approach as compared to the considered baselines.

In cloud storage, the digital data is stored in logical storage pools, backed by heterogeneous physical storage media and computing infrastructure that are managed by a cloud service provider (CSP). One of the key advantages of cloud storage is its elastic pricing mechanism, in which the users need only pay for the resources/services they actually use, e.g., depending on the storage capacity consumed, the number of file accesses per month, and the negotiated service level agreement. To balance the tradeoff between service performance and cost, CSPs often employ different storage tiers, for instance, cold storage and hot storage. Storing data in hot storage incurs high storage cost yet delivers low access latency, whereas cold storage is able to inexpensively store massive amounts of data and thus provides lower cost with higher latency. In this paper, we address a major challenge confronting the CSPs utilizing such tiered storage architecture-how to maximize their overall profit over a variety of storage tiers that offer distinct characteristics, as well as file placement and access request scheduling policies. To this end, we propose a scheme where the CSP offers a two-stage auction process for: 1) requesting storage capacity and 2) requesting accesses with latency requirements. Our two-stage bidding scheme provides a hybrid storage and access optimization framework with the objective of maximizing the CSP's total net profit over four dimensions: file acceptance decision, placement of accepted files, file access decision and access request scheduling policy. The proposed optimization is a mixed-integer nonlinear program that is hard to solve. We propose an efficient heuristic to relax the integer optimization and to solve the resulting nonlinear stochastic programs. The algorithm is evaluated under different scenarios and with different storage system parameters, and insightful numerical results are reported by comparing the proposed approach with other profit-maximization models. We see a profit increase of over 60% of our proposed method compared to other baseline algorithms in certain simulation scenarios.

Internet video traffic has been rapidly increasing and is further expected to increase with the emerging 5G applications, such as higher definition videos, the IoT, and augmented/virtual reality applications. As end users consume video in massive amounts and in an increasing number of ways, the content distribution network (CDN) should be efficiently managed to improve the system efficiency. The streaming service can include multiple caching tiers, at the distributed servers and the edge routers, and efficient content management at these locations affects the quality of experience (QoE) of the end users. In this paper, we propose a model for video streaming systems, typically composed of a centralized origin server, several CDN sites, and edge-caches located closer to the end user. We comprehensively consider different systems design factors, including the limited caching space at the CDN sites, allocation of CDN for a video request, choice of different ports (or paths) from the CDN and the central storage, bandwidth allocation, the edge-cache capacity, and the caching policy. We focus on minimizing a performance metric, stall duration tail probability (SDTP), and present a novel and efficient algorithm accounting for the multiple design flexibilities. The theoretical bounds with respect to the SDTP metric are also analyzed and presented. The implementation of a virtualized cloud system managed by Openstack demonstrates that the proposed algorithms can significantly improve the SDTP metric compared with the baseline strategies.

Deep neural networks have demonstrated state-of-the-art performance in a variety of real-world applications. In order to obtain performance gains, these networks have grown larger and deeper, containing millions or even billions of parameters and over a thousand layers. The tradeoff is that these large architectures require an enormous amount of memory, storage, and computation, thus limiting their usability. Inspired by the recent tensor ring factorization, we introduce Tensor Ring Networks (TR-Nets), which significantly compress both the fully connected layers and the convolutional layers of deep neural networks. Our results show that our TR-Nets approach is able to compress LeNet-5 by 11× without losing accuracy, and can compress the state-of-the-art Wide ResNet by 243× with only 2.3% degradation in Cifar10 image classification. Overall, this compression scheme shows promise in scientific computing and deep learning, especially for emerging resource-constrained devices such as smartphones, wearables, and IoT devices.

In this paper, we study the problem of Quality of Experience (QoE) aware resource allocation in wireless systems. In particular, we consider application-aware joint Bandwidth-Power allocation for a small cell. We optimize a QoE metric for multi-user video streaming in a small cell that maintains a trade-off between maximizing the playback rate of each user and ensuring proportional fairness (PF) among users. We formulate the application-driven joint bandwidth-power allocation as a non-convex optimization problem. However, we develop a polynomial complexity algorithm, and we show that the proposed algorithm achieves the optimal solution of the proposed optimization problem. Simulation results show that the proposed QoE-aware algorithm significantly improves the average QoE. Moreover, it outperforms the weighted sum rate allocation which is the state-of-the-art physical resource allocation scheme.

The recent framework for tiered spectrum sharing in the 3.5 GHz band establishes rules in which multiple firms called Environment Sensing Capability operators (ESCs) may measure spectrum occupancy and sell these measurements to other firms to help facilitate spectrum access. Motived by this we consider a scenario in which two spectrum access firms (SAs) seeks to access a shared band of spectrum and must in turn purchase spectrum measurements from one of two ESCs. Given the measurements they purchase, the SA firms then compete on price to serve customers in a shared band of spectrum. We study how differences in the quality and price of the spectrum measurements impact the resulting market equilibrium between the SAs and find that having different qualities of measurements available to different SAs can lead to better economic welfare.

In this letter, we study the deterministic sampling patterns for the completion of low-rank matrix, when corrupted with a sparse noise, also known as robust matrix completion. We extend the recent results on the deterministic sampling patterns in the absence of noise based on the geometric analysis on the Grassmannian manifold. A special case where each column has a certain number of noisy entries is considered, where our probabilistic analysis performs very efficiently. Furthermore, assuming that the rank of the original matrix is not given, we provide an analysis to determine if the rank of a valid completion is indeed the actual rank of the data corrupted with sparse noise by verifying some conditions.

In this paper, we consider the energy-bandwidth allocation for a network of multiple users, where the transmitters each powered by both an energy harvester and conventional grid, access the network orthogonally on the assigned frequency band. The tradeoff among the weighted sum throughput, the use of grid energy, and the amount of energy cooperation is studied through an optimization objective which is a linear combination of these quantities. To solve the problem efficiently, an iterative algorithm is proposed using the Proximal Jacobian ADMM. We show that this algorithm converges to the optimal solution with an overall complexity of O(N2K2). Numerical results show that the proposed algorithms can make efficient use of the harvested energy, grid energy, energy cooperation, and the available bandwidth.

We propose an online pricing mechanism for electric vehicle (EV) charging. A charging station decides prices for each arriving EV depending on the energy and the time within which the EV will be served (i.e. deadline). The user selects either one of the contracts by paying the prescribed price or rejects all depending on their utilities. The charging station has to select a price without knowing the future arrival times of the EVs and the utilities of the EV users. We show that there exists a social welfare pricing strategy, however, the above may not maximize the expected profit of the charging station and even the profit may be 0. We propose a fixed profit pricing strategy which provides a guaranteed fixed profit to the charging station. Numerically, we show that how the charging station can select a profit margin to trade-off between profit and the users' surpluses. We also show empirically that since our proposed mechanism also controls the deadline of the vehicles compared to the existing pricing mechanisms, hence, the number of charging spots required can be lower.

In this paper, we develop optimal energy scheduling algorithms for optical Poisson channels with energy harvesting devices. The objective is to maximize the channel sum-rate, assuming that the side information of energy harvesting states for K time slots is known a priori, and the battery capacity and the maximum energy consumption in each time slot are bounded. The problem is formulated as a convex optimization problem with O(K) constraints making it hard to solve using a general convex solver since the computational complexity of a generic convex solver is exponential in the number of constraints. This paper gives an efficient energy scheduling algorithm that has a computational complexity of O(K2). The proposed algorithm is also shown to be optimal. The proposed energy schedule is piece-wise constant, which changes when the battery overflows or depletes. Numerical results depict significant improvement of the optimal strategy over benchmark strategies.

Using the matrix product state (MPS) representation of the recently proposed tensor ring (TR) decompositions, in this paper we propose a TR completion algorithm, which is an alternating minimization algorithm that alternates over the factors in the MPS representation. This development is motivated in part by the success of matrix completion algorithms that alternate over the (low-rank) factors. We propose a novel initialization method and analyze the computational complexity of the TR completion algorithm. The numerical comparison between the TR completion algorithm and the existing algorithms that employ a low rank tensor train (TT) approximation for data completion shows that our method outperforms the existing ones for a variety of real computer vision settings, and thus demonstrates the improved expressive power of tensor ring as compared to tensor train.

Distributed storage systems are known to be susceptible to long tails in response time. It has been shown that in modern online applications such as Bing, Facebook, and Amazon, the long tail of latency is of particular concern, with 99.9th percentile response times being orders of magnitude worse than the mean. As erasure codes emerge as a popular technique in distributed storage to achieve high data reliability while attaining space efficiency, taming tail latency remains an open problem due to the lack of mathematical models for analyzing such erasure-coded storage systems. In this paper, we quantify tail latency in distributed storage systems that employ erasure coding. In particular, we derive upper bounds on tail latency in closed-form for arbitrary service time distribution and heterogeneous files. Based on the model, we formulate an optimization problem to jointly minimize weighted latency tail probability of all files. The non-convex problem is solved using an efficient, alternating optimization algorithm. Simulation results show significant reduction of tail latency for erasure-coded storage systems with realistic workload.

In this paper, we characterize the deterministic conditions on the locations of the sampled entries, which are equivalent (necessary and sufficient) to finite completability of a tensor given some components of its Tucker rank. In order to derive this characterization, we propose an algebraic geometric analysis on the Tucker manifold, which allows us to incorporate multiple rank components in the proposed analysis in contrast with the conventional geometric approaches on the Grassmannian manifold. Then, using the developed tools for this analysis, we also derive a sufficient condition on the sampling pattern that ensures there exists only one completion for the sampled tensor (unique completability).

In this paper, we consider the problem of completing a sampled matrix U = [U1|U2] given the ranks of U, U1, and U2which is known as the multi-view data completion problem. We characterize the deterministic conditions on the locations of the sampled entries that is equivalent (necessary and sufficient) to finite completability of the sampled matrix. To this end, in contrast with the existing analysis on Grassmannian manifold for a single-view matrix, i.e., conventional matrix completion, we propose a geometric analysis on the manifold structure for multi-view data to incorporate more than one rank constraint. Then, using the proposed geometric analysis, we propose sufficient conditions on the sampling pattern, under which there exists only one completion (unique completability) given the three rank constraints.

Upload and download traffic often coexist in mobile networks. However, TCP download throughput could be substantially degraded by upload traffic even if the downlink is not the bottleneck. Previous works such as RSFC and TCP-RRE can substantially improve TCP download throughput in the presence of concurrent TCP upload flows, albeit at the expense of significantly degraded upload throughput performance. This work addresses this limitation by developing a novel Aggregate Transmission Rate Controller with Upload and Download flows aggregations (ATRC-UD) to jointly accelerate concurrent TCP upload and download flows from/to the same mobile device. The insight is that existing TCP as well as other flow-based approaches all suffer from ACK packets delayed by data packets from TCP flows in the opposite direction, resulting in significant errors in bandwidth estimation. By contrast, ATRC-UD exploits data packets of the opposite direction to enable continuously estimation of the downlink bandwidth and queueing delay even when ACK packets are significantly delayed. This allows ATRC-UD to track the bandwidth and delay variations more closely to maintain a shorter queue length at the downlink, thus jointly improve the download-upload throughput. Extensive emulated and real-world experiments showed that ATRC-UD enables TCP to achieve 96% downlink bandwidth utilization while improving uplink bandwidth utilization by over 115% compared to existing approaches, such as TCP-RRE and RSFC.

Two‐way relay is potentially an effective approach to spectrum sharing and aggregation by allowing simultaneous bidirectional transmissions between source–destinations pairs. In this study, the two‐way relay network, a class of four‐unicast networks, where there are four source/destination nodes and two relay nodes, with each source sending a message to its destination, is studied. They show that without relay caching the total degrees of freedom (DoF) is bounded from above by , indicating that bidirectional links do not double the DoF (it is known that the total DoF of one‐way relay network is 2). Further, they show that the DoF of is achievable for the two‐way relay network with relay caching. Finally, even though the DoF of this network is no more than for generic channel gains, DoF of 4 can be achieved for a symmetric configuration of channel gains.

Recently, fundamental conditions on the sampling patterns have been obtained for finite completability of low-rank matrices or tensors given the corresponding ranks. In this paper, we consider the scenario where the rank is not given and we aim to approximate the unknown rank based on the location of sampled entries and some given completion. We consider a number of data models, including single-view matrix, multi-view matrix, CP tensor, tensor-train tensor and Tucker tensor. For each of these data models, we provide an upper bound on the rank when an arbitrary low-rank completion is given. We characterize these bounds both deterministically, i.e., with probability one given that the sampling pattern satisfies certain combinatorial properties, and probabilistically, i.e., with high probability given that the sampling probability is above some threshold. Moreover, for both single-view matrix and CP tensor, we are able to show that the obtained upper bound is exactly equal to the unknown rank if the lowest-rank completion is given. Furthermore, we provide numerical experiments for the case of single-view matrix, where we use nuclear norm minimization to find a low-rank completion of the sampled data and we observe that in most of the cases the proposed upper bound on the rank is equal to the true rank.

Erasure codes are widely used in distributed storage systems since they provide space-optimal data redundancy to protect against data loss. Despite recent progress on quantifying average service latency when erasure codes are employed, there is very little work on providing differentiated latency among multiple tenants that may have different latency requirements. This paper proposes a novel framework for providing and optimizing differentiated latency in erasure-coded storage by investigating two policies, weighted queue and priority queue, for scheduling tenant requests. For both policies, we quantify service latency for different tenant classes for homogeneous files with arbitrary placement and service time distributions. We develop an optimization framework that jointly minimizes differentiated latency over three decision spaces: 1) data placement; 2) request scheduling; and 3) resource management. Efficient algorithms harnessing bipartite matching and convex optimization techniques are developed to solve the proposed optimization. Our solution enables elastic service-level agreements to meet heterogeneous application requirements. We further prototype our solution with both queuing models applied in an open-source, cloud storage deployment that simulates three geographically distributed data centers through bandwidth reservations. Experimental results validate our theoretical delay analysis and show significant joint latency reduction for different classes of files, providing valuable insights into service differentiation and elastic quality of service in erasure-coded storage systems.

Modern distributed storage systems often use erasure codes to protect against disk and node failures to increase reliability, while trying to meet the latency requirements of the applications and clients. Storage systems may have caches at the proxy or client ends in order to reduce the latency. In this paper, we consider a novel caching framework with erasure code called functional caching. Functional caching involves using erasure-coded chunks in the cache such that the code formed by the chunks in storage nodes and cache combined are maximal-distance-separable erasure codes. Based on the arrival rates of different files, placement of file chunks on the servers, and the service time distribution of storage servers, an optimal functional caching placement and the access probabilities of the file request from different disks are considered. The proposed algorithm gives significant latency improvement in both simulations and a prototyped solution in an open-source, cloud storage deployment.

Cellular network providers collect and use a wide variety of data for assessing the service quality experienced by their smartphone users. The data is essential for tasks ranging from event detection, problem diagnosis, impact analysis, coverage and capacity planning, load balancing, and performance optimization. For example, service quality measurements and data from drive-by tests provide useful and detailed information about different aspects of quality of service such as dropped calls due to handovers or radio interference. However, a major challenge for effective service quality management in operational setup is the presence of missing or unavailable data. Furthermore, the cellular data is inherently multidimensional, i.e. is a function of several variables such as location, device type, and time. Motivated by recent advances in handling multidimensional data, we propose to use tensor algebraic models and methods for cellular data prediction. The main idea is to model the data as a low rank tensor and use a rank constrained interpolation for data prediction. We focus on two recently proposed algebraic models employing two different notions of tensor rank. We test and compare the performance of the two approaches on real-world data sets collected from an operational cellular network and indicate the regimes in which one method is superior to the other. Based on these observations the proposed algorithm chooses the best of the two approaches using cross-validation.

In this paper, we consider tensor completion under adaptive sampling of tensor (a multidimensional array) fibers. Tensor fibers or tubes are vectors obtained by fixing all but one index of the array. This sampling is in contrast to the cases considered so far where one performs an adaptive element-wise sampling. In this context we exploit a recently proposed algebraic framework to model tensor data [1] and model the underlying data as a tensor with low tensor tubal-rank. Under this model we then present an algorithm for adaptive sampling and recovery, which is shown to be nearly optimal in terms of sampling complexity. We apply this algorithm for robust estimation of RF fingerprints for accurate indoor localization. We show the performance on real and synthetic data sets. Compared to existing methods, that are primarily based on non-adaptive matrix completion methods, adaptive tensor completion achieves significantly better performance.

The rapid growth of data traffic in storage systems has put a significant burden on the underlying networks of cloud storage systems. Historically, a key solution to relieve this traffic burden is caching [1]. Many companies have adopted erasure-coded storage systems. However, caching for data centers when the files are encoded with an erasure code has not been studied to the best of our knowledge. This paper proposes a new functional caching approach called Sprout that can efficiently capitalize on existing file coding in erasure-coded storage systems. In contrast to exact caching that stores chunks identical to original copies, our functional caching approach forms d new data chunks, which together with the existing n chunks satisfy the property of being an (n + d, k) MDS code. Thus, the file can now be recovered from any out of n + d chunks (rather than k out of n under exact caching), effectively extending coding redundancy, as well system diversity for scheduling file access requests. The proposed functional caching approach saves latency due to more flexibility to obtain k-d chunks from the storage system a very minimal additional computational cost of creating the coded cached chunks. While quantifying service latency erasure-coded storage systems is an open problem, we generalize previous results on probabilistic scheduling policy [2,3] that distributes file requests to cache and storage nodes with optimized probabilities, and derive a closed-form upper bound on mean service latency for the proposed functional caching approach.

LTE-Advanced (LTE-A) macro-cell deployments are being enhanced with small cells, i.e., low-power base stations, to increase the network coverage and capacity. However, simultaneous co-channel transmissions from macro and small cells cause increased inter-cell interference and under-utilize the spectrum resources at the small cells. The following LTE-A design techniques are used to improve system performance in such deployments: (i) Carrier Aggregation (CA) to increase capacity by using additional carrier bandwidth; (ii) enhanced Inter-Cell Interference Coordination (elCIC), that includes (a) Cell Selection Biasing (CSB) to increase small cell spectrum utilization via cell range expansion; and (b) blanking data transmission on the macro cells for a certain duration of time to increase cell-edge user throughput Our objective is to maximize the CSB of the small cell, subject to user QoS constraints and blanking support from the macro cell. Towards this end, we develop an analytical model that captures the inter-dependency between elCIC techniques. We observe that, not accounting for the complex inter-dependencies between these techniques leads to a degraded network performance. We propose a framework that jointly optimizes elCIC and the assignment of multiple component carriers in an LTE-A deployment for increasing spectrum utilization at the small cells with appropriate blanking support from the macro cells. Our simulation results show that our approach increases the small cell spectrum utilization and aggregate cell-edge throughput by as much as 200%.

In this paper we present deterministic analysis of sufficient conditions for sparse subspace clustering under missing data, when data is assumed to come from a Union of Subspaces (UoS) model. In this context we consider two cases, namely Case I when all the points are sampled at the same co-ordinates, and Case II when points are sampled at different locations. We show that results for Case I directly follow from several existing results in the literature, while results for Case II are not as straightforward and we provide a set of dual conditions under which, perfect clustering holds true. We provide extensive set of simulation results for clustering as well as completion of data under missing entries, under the UoS model. Our experimental results indicate that in contrast to the full data case, accurate clustering does not imply accurate subspace identification and completion, indicating the natural order of relative hardness of these problems.

In this paper, we develop optimal energy-bandwidth allocation algorithms in fading channels for multiple energy harvesting transmitters. We first assume that the side information of both the channel states and the energy harvesting states is known for K time slots a priori, and the battery capacity and the maximum transmission power in each time slot are bounded. The network consists of N transmitter-receiver pairs and the objective is to maximize the sum-rate of all communication links over the K time slots by assigning the transmission power and bandwidth for each transmitter in each slot. The problem is formulated as a convex optimization problem with O(N K) constraints, where N is the number of the receivers, making it hard to solve with a generic convex solver. An iterative algorithm is proposed based on efficiently solving two subproblems in each iteration, that has an overall complexity of O(N K2). The convergence and the optimality of this algorithm are also shown. Moreover, a heuristic algorithm is also proposed for energy-bandwidth allocation based on causal information of channel and energy harvesting states. Simulation results show that the proposed causal and noncausal algorithms can make efficient use of the harvested energy and the available bandwidth. And they achieve significantly higher rates than some heuristic policies for energy and bandwidth allocation.

This letter considers localization using multiple-input multiple-output (MIMO) systems, configured with multiple transmit and receive sensors, widely distributed in a three-dimensional space. The placement of antennas is explored when the receiver hardware has varying noise quality. Cramer-Rao Lower Bounds are optimized to find the antenna placements, where it is shown that a symmetric configuration of transmitting and different quality receiving sensors around an emitter is optimal.

In this paper, we develop achievability schemes for symmetric K-user interference channels with a rate-limited feedback from each receiver to the corresponding transmitter. We study this problem under two different channel models: the linear deterministic model, and the Gaussian model. For the deterministic model, the proposed scheme achieves a symmetric rate that is the minimum of the symmetric capacity with infinite feedback, and the sum of the symmetric capacity without feedback and the symmetric amount of feedback. For the Gaussian interference channel, we use lattice codes to propose a transmission strategy that incorporates the techniques of Han-Kobayashi message splitting, interference decoding, and decode and forward. This strategy achieves a symmetric rate, which is within a constant number of bits to the minimum of the symmetric capacity with infinite feedback, and the sum of the symmetric capacity without feedback and the amount of symmetric feedback. This constant is obtained as a function of the number of users, K. We note that for the special case of Gaussian IC with K = 2, our proposed achievability scheme results in a symmetric rate that is within at most 21.085 bits/s/Hz of the outer bound, which is the first constant gap bound despite the constant gap claim in [1]. The symmetric achievable rate is used to characterize the achievable generalized degrees of freedom, which exhibits a gradual increase from no feedback to perfect feedback in the presence of feedback links with limited capacity.

Indoor localization is a supporting technology for a broadening range of pervasive wireless applications. One promising approach is to locate users with radio frequency fingerprints. However, its wide adoption in real-world systems is challenged by the time- and manpower-consuming site survey process, which builds a fingerprint databasea priorifor localization. To address this problem, we visualize the 3-D RF fingerprint data as a function of locations (x-y) and indices of access points (fingerprint), as atensorand use tensor algebraic methods for anadaptivetubal-sampling of this fingerprint space. In particular, using a recently proposed tensor algebraic framework in[1], we capture the complexity of the fingerprint space as a low-dimensional tensor-column space. In this formulation, the proposed scheme exploits adaptivity to identify reference points which are highly informative for learning this low-dimensional space. Further, under certain incoherency conditions, we prove that the proposed scheme achieves bounded recovery error and near-optimal sampling complexity. In contrast to several existing work that rely on random sampling, this paper shows that adaptivity in sampling can lead to significant improvements in localization accuracy. The approach is validated on both data generated by the ray-tracing indoor model which accounts for the floor plan and the impact of walls and the real world data. Simulation results show that, while maintaining the same localization accuracy of existing approaches, the amount of samples can be cut down by$71$percent for the high SNR case and$55$percent for the low SNR case.

Proportional Fair (PF) scheduling algorithms are the de facto standard in cellular networks. They exploit the users' channel state diversity (induced by fast-fading) and are optimal for stationary channel state distributions and an infinite time-horizon. However, mobile users experience a nonstationary channel, due to slow-fading (on the order of seconds), and are associated with base stations for short periods. Hence, we develop the Predictive Finite-horizon PF Scheduling ((PF)2S) Framework that exploits mobility. We present extensive channel measurement results from a 3G network and characterize mobility-induced channel state trends. We show that a user's channel state is highly reproducible and leverage that to develop a data rate prediction mechanism. We then present a few channel allocation estimation algorithms that exploit the prediction mechanism. Our trace-based simulations consider instances of the (PF)2S Framework composed of combinations of prediction and channel allocation estimation algorithms. They indicate that the framework can increase the throughput by 15%-55% compared to traditional PF schedulers, while improving fairness.

In most wireless networks, nodes have only limited local information about the state of the network, which includes connectivity and channel state information. With limited local information about the network, each node's knowledge is mismatched; therefore, they must make distributed decisions. In this paper, we pose the following question: If every node has network state information only about a small neighborhood, how and when should nodes choose to transmit? While link scheduling answers the above question for point-to-point physical layers that are designed for an interference-avoidance paradigm, we look for answers in cases when interference can be embraced by advanced PHY-layer design, as suggested by results in network information theory. To make progress on this challenging problem, we propose a constructive distributed algorithm that achieves rates higher than link scheduling based on interference avoidance, especially if each node knows more than one hop of network state information. We compare our new aggressive algorithm to a conservative algorithm we have presented in a 2013 conference paper. Both algorithms schedule subnetworks such that each subnetwork can employ advanced interference-embracing coding schemes to achieve higher rates. Our innovation is in the identification, selection, and scheduling of subnetworks, especially when subnetworks are larger than a single link.

Modern distributed storage systems offer large capacity to satisfy the exponentially increasing need of storage space. They often use erasure codes to protect against disk and node failures to increase reliability, while trying to meet the latency requirements of the applications and clients. This paper provides an insightful upper bound on the average service delay of such erasure-coded storage with arbitrary service time distribution and consisting of multiple heterogeneous files. Not only does the result supersede known delay bounds that only work for a single file or homogeneous files, it also enables a novel problem of joint latency and storage cost minimization over three dimensions: selecting the erasure code, placement of encoded chunks, and optimizing scheduling policy. The problem is efficiently solved via the computation of a sequence of convex approximations with provable convergence. We further prototype our solution in an open-source cloud storage deployment over three geographically distributed data centers. Experimental results validate our theoretical delay analysis and show significant latency reduction, providing valuable insights into the proposed latency-cost tradeoff in erasure-coded storage.

We consider multiple transmission links in a frequency-selective fading channel, where the transmitters are powered by renewable energy sources that provide variable amount of energy at different times. We formulate the problem of joint energy and subchannel allocation for all transmitters over a scheduling period, as a mixed integer program. Assuming that the harvested energy and subchannel gains can be predicted, we propose an algorithm to efficiently obtain the energy-subchannel allocations for all links over the scheduling period based on controlled water-filling. The proposed algorithm is shown to be asymptotically optimal when the bandwidth of the subchannel goes to zero. A causal algorithm is also proposed based on the Q-learning technique that makes use of the statistics of the energy harvesting and channel fading processes. Simulation results demonstrate that the performance of the proposed noncausal algorithm is close to the upper-bound on the optimal performance and the proposed causal algorithm outperforms various heuristic allocation policies.

This paper proposes an approach to minimize service latency in a data center network where erasure-coded files are stored on distributed disks/racks and access requests are scattered across the network. Due to limited bandwidth available at both top-of-the-rack and aggregation switches, network bandwidth must be apportioned among different intra-and inter-rack data flows in line with their traffic statistics. We formulate this problem as weighted queuing and employ a class of probabilistic request scheduling policies to derive a closed-form outer-bound of service latency for erasure-coded storage with arbitrary file access patterns and service time distributions. The result enables us to propose a joint latency optimization over three entangled "control knobs": the bandwidth allocation at top-of-the-rack and aggregation switches, the probabilities for scheduling file requests, and the placement of encoded file chunks, which affects data locality. The joint optimization is shown to be a mixed-integer problem. We develop an iterative algorithm which decouples and solves the joint optimization as three sub-problems, which are either convex or solvable via bipartite matching in polynomial time. The proposed algorithm is prototyped in an open-source, distributed file system, Tahoe, and evaluated on a cloud tested with 16 separate physical hosts in an Open Stack cluster. Experiments validate our theoretical latency analysis and show significant latency reduction for diverse file access patterns. The results provide valuable insight on designing low-latency data center networks with erasure-coded storage.

Cloud computing has recently emerged as a new technology for hosting and supplying services over the Internet. This technology has brought many benefits, such as eliminating the need for maintaining expensive computing hardware and allowing business owners to start from small and increase resources only when there is a rise in service demand. With an increasing demand for cloud computing, providing performance guarantees for applications that run over cloud become important. Applications can be abstracted into a set of virtual machines with certain guarantees depicting the quality of service of the application. In this paper, we consider the placement of these virtual machines across multiple data centers, meeting the quality of service requirements while minimizing the bandwidth cost of the data centers. This problem is a generalization of the NP-hard Generalized Quadratic Assignment Problem (GQAP). We formalize the problem and propose a novel algorithm based on a biased random-key genetic algorithm (BRKGA) to find near-optimal solutions for the problem. The experimental results show that the proposed algorithm is effective in quickly finding feasible solutions and it produces better results than a baseline aproach provided by a commercial solver and a multi-start algorithm.

The effect of coding on content retrieval latency in data center storage system is drawing more and more significant attention these days, and customizing elastic service latency for the tenants is undoubtedly appealing to cloud storage, but it also comes with great technical challenges: due to the lack of analytic latency models for erasure-coded storage, most of the literature is limited to the analysis of average service latency, e.g., [1], [2], having assumptions like homogeneous files, exponential service time distribution [3], fixed erasure codes [4], which is unsuitable for a multi-tenant cloud environment where each tenant has a different latency requirement for accessing files in an erasure-coded, online cloud storage. Optimizing differentiated service delay in an erasure-coded storage system is an open problem. This work considers an erasure-coded storage with multiple tenants and differentiated delay demands, studies two types of service policies, non-preemptive priority queue and weighted queue, quantifying service latency of these policies, propose a novel optimization framework that provides differentiated service latency to meet heterogeneous application requirements in cloud storage.

LTE network service reliability is highly dependent on the wireless coverage that is provided by cell towers (eNB). Therefore, the network operator's response to outage scenarios needs to be fast and efficient, in order to minimize any degradation in the Quality of Service (QoS). In this paper, we propose an outage mitigation framework for LTE-Advanced (LTE-A) wireless networks. Our framework exploits the inherent design features of LTE-A; it performs a dual optimization of the transmission power and beamforming weight parameters at each neighbor cell sector of the outage eNBs, while taking into account both the channel characteristics and residual eNB resources, after serving its current traffic load. Assuming statistical Channel State Information about the users at the eNBs, we show that this problem is theoretically NP-hard; thus we relax it as a convex optimization problem and solve for the optimal points using an iterative algorithm. Contrary to previously-proposed power control studies, our framework is specifically designed to alleviate the effects of sudden LTE-A eNB outages, where a large number of mobile users need to be efficiently offloaded to nearby towers. We present the detailed analytical design of our framework, and we assess its efficacy via extensive NS-3 simulations on an LTE-A topology. Our simulations demonstrate that our framework provides adequate coverage and QoS across all examined outage scenarios.

In this paper, we study the capacity regions of two-way linear deterministic diamond channels. We show that the capacity of the diamond channel in each direction can be simultaneously achieved for all values of channel parameters, where the forward and backward channel parameters are not necessarily the same. We propose a relay strategy called `reverse amplify-and-forward' strategy and show that this strategy and its variants combined with proper transmission strategies achieve the capacity of linear deterministic diamond channel.

In this paper, we consider the energy-bandwidth allocation for a network with multiple orthogonal broadcast channels, where each transmitter communicates with multiple receivers orthogonally. We assume that the harvested energy and channel gain of each transmitter can be predicted for K slots a priori. To maximize the weighted throughput of the network, we formulate an optimization problem with O(MK) constraints, where M is the number of the receivers, making it hard to solve using a generic convex solver since the computational complexity of the solver becomes impractically high when the number of constraints is large. In order to use the iterative algorithm proposed in [1] to solve the problem efficiently, we decompose the problem into the energy and bandwidth allocation subproblems and propose algorithms to solve the two corresponding subproblems, so that the optimal energy-bandwidth allocation can be obtained with an overall complexity of O(MK2).

We consider an energy harvesting network with multiple transmission links in a frequency-selective fading channel. We formulate the problem of joint energy and subchannel allocation for all transmitters over a scheduling period, as a mixed integer program. With the predictions of the harvested energy and subchannel gains, we propose an algorithm to efficiently obtain the energy-subchannel allocations for all links over the scheduling period based on controlled water-filling. The proposed algorithm is shown to be asymptotically optimal when the bandwidth of the subchannel goes to zero. Simulation results demonstrate that the performance of the proposed algorithm is close to the upper-bound on the optimal performance, which is also outperforms various heuristic allocation policies.

We consider an energy harvesting point-to-point communication system where the transmitter is powered by an energy arrival process and is equipped with a battery of finite capacity Bmax, which could be used for saving energy for future use. We assume a discrete i.i.d. energy arrival process where at each time step, energy of amount Ai is harvested with probability pi Vi ∈ {1, 2, .. ., K} independent of the other time steps. We provide upper and lower bounds on the capacity of this channel. These bounds are shown to be within a constant gap for K ≤ 3 for all parameters, and for K > 3 when the battery capacity Bmax is small or large enough, where this constant does not depend on any energy or battery parameters.

In this paper, we develop optimal energy scheduling algorithms for N-user fading multiple-access channels with energy harvesting to maximize the channel sum-rate, assuming that the side information of both the channel states and energy harvesting states for K time slots is known a priori, and the battery capacity and the maximum energy consumption in each time slot are bounded. The problem is formulated as a convex optimization problem with O (NK) constraints making it hard to solve using a general convex solver since the computational complexity of a generic convex solver becomes impractically high when the number of constraints is large. This paper gives an efficient energy scheduling algorithm, called the iterative dynamic water-filling algorithm, that has a computational complexity of O(NK2) per iteration. For the single-user case, a dynamic water-filling method is shown to be optimal. Unlike the traditional water-filling algorithm, in dynamic water-filling, the water level is not constant but changes when the battery overflows or depletes. An iterative version of the dynamic water-filling algorithm is shown to be optimal for the case of multiple users. Even though in principle the optimality is achieved under large number of iterations, in practice convergence is reached in only a few iterations. Moreover, a single iteration of the dynamic water-filling algorithm achieves a sum-rate that is within (N-1)K nats of the optimal sum-rate.

In this paper, we consider the energy-bandwidth allocation for a network with multiple broadcast channels, where the transmitters each powered by an energy harvester, access the network orthogonally on the assigned frequency band and each transmitter communicates with multiple receivers orthogonally or non-orthogonally. We assume that the energy harvesting state and channel gain of each transmitter can be predicted for K time slots a priori. To maximize the weighted throughput, we formulate an optimization problem with O(MK) constraints, where M is the total number of receivers, and optimize over the energy and bandwidth allocation variables. To solve the problem efficiently, an iterative algorithm is proposed that alternatively solves the two subproblems of energy allocation and bandwidth allocation in each iteration. We show that this algorithm converges to the optimal solution. Also, we propose efficient algorithms to solve the two subproblems, so that the optimal energy-bandwidth allocation can be obtained with an overall complexity of O(MK2), even though the problem is non-convex when the broadcast channel is non-orthogonal. Simulation results show that the proposed algorithms can make efficient use of the harvested energy and the available bandwidth, and achieve significantly better performance as compared to some heuristic policies for energy and bandwidth allocation. Moreover, it is seen that with energy-harvesting transmitters, the non-orthogonal broadcast channel offers limited gain over the orthogonal broadcast channel.

In this paper, we study the capacity regions of two-way diamond channels. We show that for a linear deterministic model the capacity of the diamond channel in each direction can be simultaneously achieved for all values of channel parameters, where the forward and backward channel parameters are not necessarily the same. We divide the achievability scheme into three cases, depending on the forward and backward channel parameters. For the first case, we use a reverse amplify-and-forward strategy in the relays. For the second case, we use four relay strategies based on the reverse amplify-and-forward with some modifications in terms of replacement and repetition of some stream levels. For the third case, we use two relay strategies based on performing two rounds of repetitions in a relay. The proposed schemes for deterministic channels are used to find the capacity regions within constant gaps for two special cases of the Gaussian two-way diamond channel. First, for the general Gaussian two-way relay channel, the capacity within a constant gap is achieved with a simpler coding scheme as compared with the prior works. Then, a special symmetric Gaussian two-way diamond model is considered and the capacity region is achieved within four bits.

A new class of exact-repair regenerating codes is constructed by stitching together shorter erasure correction codes, where the stitching pattern can be viewed as block designs. The proposed codes have the help-by-transfer property where the helper nodes simply transfer part of the stored data directly, without performing any computation. This embedded error correction structure makes the decoding process straightforward, and in some cases the complexity is very low. We show that this construction is able to achieve performance better than space-sharing between the minimum storage regenerating codes and the minimum repair-bandwidth regenerating codes, and it is the first class of codes to achieve this performance. In fact, it is shown that the proposed construction can achieve a nontrivial point on the optimal functional-repair tradeoff, and it is asymptotically optimal at high rate, i.e., it asymptotically approaches the minimum storage and the minimum repair-bandwidth simultaneously.

The reliability of erasure-coded distributed storage systems, as measured by the mean time to data loss (MTTDL), depends on the repair bandwidth of the code. Repair-efficient codes provide reliability values several orders of magnitude better than conventional erasure codes. Current state of the art codes fix the number of helper nodes (nodes participating in repair) a priori. In practice, however, it is desirable to allow the number of helper nodes to be adaptively determined by the network traffic conditions. In this work, we propose an opportunistic repair framework to address this issue. It is shown that there exists a threshold on the storage overhead, below which such an opportunistic approach does not lose any efficiency from the optimal storage-repair-bandwidth tradeoff; i.e. it is possible to construct a code simultaneously optimal for different numbers of helper nodes. We further examine the benefits of such opportunistic codes, and derive the MTTDL improvement for two repair models: one with limited total repair bandwidth and the other with limited individual-node repair bandwidth. In both settings, we show orders of magnitude improvement in MTTDL. Finally, the proposed framework is examined in a network setting where a significant improvement in MTTDL is observed.

Proportional Fair (PF) scheduling algorithms are the de-facto standard in cellular networks. They exploit the users' channel state diversity (induced by fast-fading), and are optimal for stationary channel state distributions and an infinite time-horizon. However, mobile users experience a non-stationary channel, due to slow-fading (on the order of seconds), and are associated with basestations for short periods. Hence, we develop the Predictive Finite-horizon PF Scheduling ((PF)2S) Framework that exploits mobility. We present extensive channel measurement results from a 3G network and characterize mobility-induced channel state trends. We show that a user's channel state is highly reproducible and leverage that to develop a data rate prediction mechanism. We then present a few channel allocation estimation algorithms that rely on the prediction mechanism. Our trace-based simulations consider instances of the PF2S Framework composed of combinations of prediction and channel allocation estimation algorithms. They indicate that the framework can increase the throughput by 15%–55% compared to traditional PF schedulers, while improving fairness.

We develop optimal energy-bandwidth allocation algorithm for the energy harvesting transmitters in interference networks. We assume that both the channel gain and the harvested energy are known for K slots as a priori, and the battery capacity is finite. The problem is formulated as a convex optimization problem with O(NK) constraints, making it hard to solve efficiently with a generic convex solver. To efficiently obtain the optimal energy-bandwidth allocation for each transmitter in each time slot, an iterative algorithm is proposed based on solving two subproblems with efficient algorithms, that has an overall complexity of O(NK2). Moreover, the numerical results show that the proposed iterative algorithm achieves the optimal performance, providing a significant improvement as compared to some naive allocation policies.

Recent studies have shown that web browsing is one of the most prominent cellular applications. It is therefore important for cellular network operators to understand how radio network characteristics (such as signal strength, handovers, load, etc.) influence users' web browsing Quality-of-Experience (web QoE). Understanding the relationship between web QoE and network characteristics is a pre-requisite for cellular network operators to detect when and where degraded network conditions actually impact web QoE. Unfortunately, cellular network operators do not have access to detailed server-side or client-side logs to directly measure web QoE metrics, such as abandonment rate and session length. In this paper, we first devise a machine-learning-based mechanism to infer web QoE metrics from network traces accurately. We then present a large-scale study characterizing the impact of network characteristics on web QoE using a month-long anonymized dataset collected from a major cellular network provider. Our results show that improving signal-to-noise ratio, decreasing load and reducing handovers can improve user experience. We find that web QoE is very sensitive to inter-radio-access-technology (IRAT) handovers. We further find that higher radio data link rate does not necessarily lead to better web QoE. Since many network characteristics are interrelated, we also use machine learning to accurately model the influence of radio network characteristics on user experience metrics. This model can be used by cellular network operators to prioritize the improvement of network factors that most influence web QoE.

We consider power allocation for an access-controlled transmitter with energy harvesting capability based on causal observations of the channel fading state. We assume that the system operates in a time-slotted fashion and the channel gain in each slot is a random variable which is independent across slots. Further, we assume that the transmitter is solely powered by a renewable energy source and the energy harvesting process can practically be predicted. With the additional access control for the transmitter and the maximum power constraint, we formulate the stochastic optimization problem of maximizing the achievable rate as a Markov decision process (MDP) with continuous state. To efficiently solve the problem, we define an approximate value function based on a piecewise linear fit in terms of the battery state. We show that with the approximate value function, the update in each iteration consists of a group of convex problems with a continuous parameter. Moreover, we derive the optimal solution to these convex problems in closed-form. Further, we propose power allocation algorithms for both the finite- and infinite-horizon cases, whose computational complexity is significantly lower than that of the standard discrete MDP method but with improved performance. Extension to the case of a general payoff function and imperfect energy prediction is also considered. Finally, simulation results demonstrate that the proposed algorithms closely approach the optimal performance.

This paper gives the approximate capacity region of a two-user multiple-input multiple-output (MIMO) interference channel with limited receiver cooperation, where the gap between the inner and outer bounds is in terms of the total number of receive antennas at the two receivers and is independent of the actual channel values. The approximate capacity region is then used to find the degrees of freedom region. For the special case of symmetric interference channels, we also find the amount of receiver cooperation in terms of the backhaul capacity beyond, which the degrees of freedom do not improve. Further, the generalized degrees of freedom is found for MIMO interference channels with equal number of antennas at all nodes. It is shown that the generalized degrees of freedom improves gradually from a W curve to a V curve with increase in cooperation in terms of the backhaul capacity.

In most wireless networks, nodes have only limited local information about the network state, which includes connectivity and channel state information. With limited local information about the network, each node's knowledge is mismatched, therefore they must make distributed decisions. In this paper, we pose the following question - if every node has network state information only about a small neighborhood, how and when should nodes choose to transmit? While scheduling answers the above question for point-to-point physical layers which are designed for an interference-avoidance paradigm, we look for answers in cases when interference can be embraced by advanced code design, as suggested by results in network information theory. To make progress on this challenging problem, we propose a distributed algorithm which achieves rates higher than interference-avoidance based link scheduling, especially if each node knows more than one hop of network state information.

In this paper, we investigate the effect of feedback on two-user MIMO interference channels. At first, the capacity region of MIMO interference channels with feedback is characterized within a constant number of bits, where this constant is independent of the channel matrices. Further, the generalized degrees of freedom region for the MIMO interference channel with feedback is characterized.

A new class of exact-repair regenerating codes is constructed by combining two layers of erasure correction codes together with combinatorial block designs. The proposed codes have the “uncoded repair” property where the nodes participating in the repair simply transfer part of the stored data directly, without performing any computation. The layered error correction structure results in a low-complexity decoding process. An analysis of our coding scheme is presented. This construction is able to achieve better performance than timesharing between the minimum storage regenerating codes and the minimum repair-bandwidth regenerating codes.

In this paper, we study the effect of feedback on the two-user MIMO interference channel. The capacity region of the MIMO interference channel with feedback is characterized within a constant number of bits, where this constant is independent of the channel matrices. Further, it is shown that the capacity region of the MIMO interference channel with feedback and its reciprocal interference channel are within a constant number of bits. Finally, the generalized degrees of freedom region for the MIMO interference channel with feedback is characterized.

In this paper, we study the impact of different channel output feedback architectures on the capacity of the two-user interference channel. For a two-user interference channel, a feedback link can exist between receivers and transmitters in nine canonical architectures (see Fig. 3 ), ranging from only one feedback link to four feedback links. We derive the exact capacity region for the symmetric deterministic interference channel and the constant-gap capacity region for the symmetric Gaussian interference channel for all of the nine architectures. We show that for a linear deterministic symmetric interference channel, in the weak interference regime, all models of feedback, except the one, which has only one of the receivers feeding back to its own transmitter, have the identical capacity region. When only one of the receivers feeds back to its own transmitter, the capacity region is a strict subset of the capacity region of the rest of the feedback models in the weak interference regime. However, the sum-capacity of all feedback models is identical in the weak interference regime. Moreover, in the strong interference regime, all models of feedback with at least one of the receivers feeding back to its own transmitter have the identical sum-capacity. For the Gaussian interference channel, the results of the linear deterministic model follow, where capacity is replaced with approximate capacity.

Virtualized cloud-based services can take advantage of statistical multiplexing across applications to yield significant cost savings. However, achieving similar savings with real-time services can be a challenge. In this paper, we seek to lower a provider's costs for real-time IPTV services through a virtualized IPTV architecture and through intelligent time-shifting of selected services. Using Live TV and Video-on-Demand (VoD) as examples, we show that we can take advantage of the different deadlines associated with each service to effectively multiplex these services. We provide a generalized framework for computing the amount of resources needed to support multiple services, without missing the deadline for any service. We construct the problem as an optimization formulation that uses a generic cost function. We consider multiple forms for the cost function (e.g., maximum, convex and concave functions) reflecting the cost of providing the service. The solution to this formulation gives the number of servers needed at different time instants to support these services. We implement a simple mechanism for time-shifting scheduled jobs in a simulator and study the reduction in server load using real traces from an operational IPTV network. Our results show that we are able to reduce the load by ~24%(compared to a possible ~31.3% as predicted by the optimization framework).

The capacity of insertion channels, even in the presence of feedback, is an open problem in information theory. In this paper, we prove that the capacity of insertion channel with non-causal insertion information at the transmitter is 1 even when the receiver do not know the insertion pattern. This paper considers two insertion models, namely random insertion model and the sticky insertion model. For both these models, interference-free capacity of 1 is obtained even when the receiver does not know the interference (insertion pattern).

Full duplex communication requires nodes to cancel their own signal which appears as an interference at their receive antennas. Recent work has experimentally demonstrated the feasibility of full duplex communications using software radios. In this paper, we address capacity comparisons when the total amount of analog radio hardware is bounded. Under this constraint, it is not immediately clear if one should use these radios to perform full-duplex self-interference cancellation or use the radios to give additional MIMO multiplexing advantage. We find that repurposing radios for cancellation, instead of using all of them for half-duplex over-the-air transmission, can be beneficial since the resulting full-duplex system performs better in some practical SNR regimes and almost always outperforms half duplex in symmetric degrees-of-freedom (large SNR regime).

Due to the large size of wireless networks, it is often impractical for nodes to track changes in the complete network state. As a result, nodes have to make distributed decisions about their transmission and reception parameters based on their local view of the network. In this paper, we characterize the impact of distributed decisions on the global network performance in terms of achievable sum rates. We first formalize the concept of local view by proposing a protocol abstraction using the concept of local message passing. In the proposed protocol, nodes forward information about the network state to other neighboring nodes, thereby allowing network-state information to trickle to all the nodes. The protocol proceeds in rounds, where all transmitters send a message followed by a message by all receivers. The number of rounds then provides a natural metric to quantify the extent of local information at each node. We next study two network connectivities, Z-channel, and a three-user double Z-channel. In each case, we characterize achievable sum rate with partial message passing leading to two main results. First, in many cases, nodes can make distributed decisions with only local information about the network and can still achieve the same sum capacity as can be attained with global information irrespective of the actual channel gains. We label such schemes as universally optimal. Second, for the case of three-user double Z-channel, we show that universal optimality is not achievable if the per node information is below a threshold. In fact, distributed decisions can lead to unbounded losses compared to full information case for some channel gains.

The end to end system data performance over a 3G cellular network depends on many factors such as the number of users, interference, multipath propagation, radio resource management techniques as well as the interaction between these mechanisms and the transport protocol's flow and congestion mechanisms. Using controlled experiments in a public cell site, we investigate the interaction between TCP and the 3G UMTS/HSPA network's resource allocation, and its effect on fairness in the throughput achieved across multiple (up to 26) TCP flows in a loaded cell sector. Our field measurement results indicate that TCP fairness fluctuates significantly when the air interface (radio link) is the bottleneck. We also observe that TCP fairness is substantially better when the backhaul link (a fixed wired link) is the bottleneck, instead of the air interface. We speculate that the fairness of TCP flows is adversely impacted by the mismatch between the resource allocation mechanisms of TCP's flow and congestion control and that of the Radio Access Network (RAN).

This paper investigates the effect of eavesdroppers on network connectivity, using a wiretap model and percolation theory. The wiretap model captures the effect of eavesdroppers on link security. A link exists between two nodes only if the secrecy capacity of that link is positive. Network connectivity is defined in a percolation sense, i.e., connectivity exists if an infinite connected component exists in the corresponding secrecy graph. We consider uncertainty in location of eavesdroppers, which is modeled directly at the network level as correlated failures in the secrecy graph. Our approach attempts to bridge the gap between physical layer security under uncertain channel state information and network level connectivity under secrecy constraints. For square and triangular lattice secrecy graphs, we obtain bounds on the percolation threshold, which is the critical value of the probability of occurrence of an eavesdropper, above which network connectivity does not exist. For Poisson secrecy graphs, degree distribution and mean value of upper and lower bounds on node degree are obtained. Further, inner and outer bounds on the achievable region for network connectivity are obtained. Both analytic and simulation results show that uncertainty in location of eavesdroppers has a dramatic effect on network connectivity in a secrecy graph.

“If we know more, we can achieve more.” This adage also applies to communication networks, where more information about the network state translates into higher sum-rates. In this paper, we formalize this increase of sum-rate with increased knowledge of the network state. The knowledge of network state is measured in terms of the number of hops,h, of information available to each transmitter and is labeled ash-local view. To understand how much capacity is lost due to limited information, we propose to use the metric of normalized sum-capacity, which is theh-local view sum-capacity divided by global-view sum capacity. For the cases of one and two-local view, we characterize the normalized sum-capacity for many classes of deterministic and Gaussian interference networks. In many cases, a scheduling scheme called maximal independent graph scheduling is shown to achieve normalized sum-capacity. We also show that its generalization for 1-local view, labeled coded set scheduling, achieves normalized sum-capacity in some cases where its uncoded counterpart fails to do so.

Most communication systems use some form of feedback, often related to channel state information. In this paper, we study diversity multiplexing tradeoff for both frequency division duplex (FDD) and time division duplex (TDD) systems, when both receiver and transmitter knowledge about the channel is noisy and potentially mismatched. For FDD systems, we first extend the achievable tradeoff region for 1.5 rounds of message passing to get higher diversity compared to the best known scheme, in the regime of higher multiplexing gains. We then break the mold of all current channel state based protocols by using multiple rounds of conferencing to extract more bits about the actual channel. This iterative refinement of the channel increases the diversity order with every round of communication. The protocols are on-demand in nature, using high powers for training and feedback only when the channel is in poor states. The key result is that the diversity multiplexing tradeoff with perfect training and$K$levels of perfect feedback can be achieved, even when there are errors in training the receiver and errors in the feedback link, with a multiround protocol which has$K$rounds of training and$K-1$rounds of binary feedback. The above result can be viewed as a generalization of Zheng and Tse, and Aggarwal and Sabharwal, where the result was shown to hold for$K=1$and$K=2$, respectively. For TDD systems, we also develop new achievable strategies with multiple rounds of communication between the transmitter and the receiver, which use the reciprocity of the forward and the feedback channel. The multiround TDD protocol achieves a diversity-multiplexing tradeoff which uniformly dominates its FDD counterparts, where no channel reciprocity is available.

In distributed wireless networks, nodes often do not have access to complete network information (e.g. network topology, channel gains, etc.). As a result, they have to execute their transmission and reception strategies with partial information about the network, in a distributed fashion. Thus, the key question is how good are the distributed decisions in comparison to the optimal decisions based on full network knowledge. In this paper, we formalize the concept of partial-information sum-capacity by defining normalized sum-capacity, which is defined as the maximum achievable fraction of full-information sum-capacity with a given amount of partial information. We then examine four deterministic networks, multiple access, multiuser Z-channel chain, one-to-many and many-to-one interference channel, and characterize the normalized sum-capacity. For each network, two cases of partial network information are analyzed: (a) each transmitter only knows the channel gains to its receiver, and (b) transmitters knows the channel gains of all links which are no more than two hops away. Quite interestingly, we show that in all eight cases (4 networks × 2 forms of partial information), the normalized sum-capacity is achieved by scheduling subnetworks for which there exist a universally optimal distributed strategy with the available partial information. Furthermore, we show that while actual sum-capacity is not known in all cases, normalized sum-capacity can be in fact be exactly characterized.

In this paper, we consider end-to-end secure communication in a large wireless network, where the locations of eavesdroppers are uncertain. Our framework attempts to bridge the gap between physical layer security under uncertain channel state information of the eavesdropper and network level connectivity under security constraints, by modeling location uncertainty directly at the network level as correlated node and link failures in a secrecy graph. Bounds on the percolation threshold are obtained for square and triangular lattices, and bounds on mean degree are obtained for Poisson secrecy graphs. Both analytic and simulation results show the dramatic effect of uncertainty in location of eavesdroppers on connectivity in a secrecy graph.

In a two-user interference channel, there are four possible feedback paths - two from each receiver to the transmitters. This leads to 16 possible models of feedback. In this paper, we derive the sum capacity of two user deterministic interference channel for all sixteen cases. We find that whenever any of the direct link feedback from a receiver to its own transmitter is present, the sum-capacity is the same as when all four feedback links are present. Further when no direct link feedback is present, the sum capacity with one cross-link feedback and two cross-links of feedback is the same. This sum-capacity is the same as the sum-capacity when there is no feedback except in the regime of interference in which both interfering links are weaker than both the direct-links in which case the sum-capacity is the same as sum-capacity of the feedback model with all four feedback links.

Most communication systems use some form of feedback, often related to channel state information. The common models used in analyses either assume perfect channel state information at the receiver and/or noiseless state feedback links. However, in practical systems, neither is the channel estimate known perfectly at the receiver and nor is the feedback link perfect. In this paper, we study the achievable diversity multiplexing tradeoff using i.i.d. Gaussian codebooks, considering the errors in training the receiver and the errors in the feedback link for frequency division duplex (FDD) systems, where the forward and the feedback are independent multiple input multiple output (MIMO) channels. Our key result is that the maximum diversity order with one-bit of feedback information is identical to systems with more feedback bits. Thus, asymptotically inSNR, more than one bit of feedback does not improve the system performance at constant rates. Furthermore, the one-bit diversity-multiplexing performance is identical to the system which has perfect channel state information at the receiver along with noiseless feedback link. This achievability uses novel concepts of power controlled feedback and training, which naturally surface when we consider imperfect channel estimation and noisy feedback links. In the process of evaluating the proposed training and feedback protocols, we find an asymptotic expression for the joint probability of theSNRexponents of eigenvalues of the actual channel and the estimated channel which may be of independent interest.

The wiretap channel type II with an active eavesdropper is considered in this paper. Compared with the eavesdropper model considered in much of the literature, the eavesdropper considered here can not only overhear but also modify the signal transmitted over the channel. Two modification models are considered. In the first model, the eavesdropper erases the bits it observes. In the second model, the eavesdropper modifies the bits it observes. For this channel with memory (introduced by the activity of the eavesdropper), one should conduct the worst case scenario analysis. Novel concatenated coding schemes that provide perfect security for the communications are developed for both models to give bounds on the achievable secrecy rate. The technique to modify the inner code to maintain the secrecy properties of the outer code may be of independent interest.

In distributed wireless networks, nodes often do not know the topology (network size, connectivity and the channel gains) of the network. Thus, they cannot compute their own maximum transmission rate and appropriate transmission scheme. In this paper, we address the inter-related problems of learning the network and the associated best achievable rates. To make progress, we will focus on K-user deterministic interference networks. First, we propose a message passing algorithm which allows nodes to incrementally learn the network topology. In each round of message passing, nodes forward what they believe is the new information to their neighbors and thus the network topology information trickles via broadcasts. Next, we consider two special examples of Z-channel and double-Z interference network and determine the sum-rate points with incomplete network information at different nodes. We show that the sum-rate point can in fact be achieved with less than full information at all the nodes but in general, less network information implies reduced set of achievable rates. In order to analyze the performance of a double-Z interference network with limited information, we find the capacity region of a deterministic double-Z interference network with full information, which is of independent interest.

The standard approach to quantum fault tolerance is to calculate error thresholds on basic gates in the limit of arbitrarily many concatenation levels. In contrast this paper takes the number of qubits and the target implementation accuracy as given, and provides a framework for engineering the constrained quantum system to the required tolerance. The approach requires solving the full dynamics of the quantum system for an arbitrary admixture (biased or unbiased) of Pauli errors. The inaccuracy between ideal and implemented quantum systems is captured by the supremum of the Schatten-k norm of the difference between the ideal and implemented density matrices taken over all density matrices. This is a more complete analysis than the standard approach, where an intricate combination of worst case assumptions and combinatorial analysis is used to analyze the special case of equiprobable errors. Conditions for fault tolerance are now expressed in terms of error regions rather than a single number (the standard error threshold). In the important special case of a stochastic noise model and a single logical qubit, an optimization over all 2×2 density matrices is required to obtain the full dynamics. The complexity of this calculation is greatly simplified through reduction to an optimization over only three projectors. Error regions are calculated for the standard 5- and 7-qubit codes. Knowledge of the full dynamics makes it possible to design sophisticated concatenation strategies that go beyond repeatedly using the same code, and these strategies can achieve target fault tolerance thresholds with fewer qubits.

The secrecy capacity of relay channels with orthogonal components is studied in the presence of additional passive eavesdropper nodes. The relay and destination receive signals from the source on two orthogonal channels such that the destination also receives transmissions from the relay on its channel. The eavesdropper(s) can overhear either one or both of the orthogonal channels. For a single eavesdropper node, the secrecy capacity is shown to be achieved by apartial decode-and-forward(PDF) scheme when the eavesdropper can overhear only one of the two orthogonal channels. For the case of two eavesdropper nodes, secrecy capacity is shown to be achieved by PDF for a sub-class of channels.

As more and more video content is made available and accessed on-demand, content and service providers face challenges of scale. Today's delivery mechanisms, especially unicast, require resources to scale linearly with the number of receivers and library sizes. Unlike these mechanisms, with multicast, the load on a server is relatively independent of the number of receivers. Adopting multicast for on-demand access, however, is challenging because of the need to temporally aggregate requests. In this paper, we investigate the importance of an intelligent scheduler and a good data model for achieving good aggregation of requests into multicast groups. We examine the use of an Earliest Deadline First (EDF)-like scheduler that aims to schedule the transmission of chunks of video according to their deadlines using multicast. We show through analysis that this approach is optimal in terms of the data transmitted by the server. Using trace data from an operational service, we show that our approach reduces server bandwidth by as much as 65% compared to traditional techniques such as unicast and cyclic multicast. Finally, our approach achieves good aggregation even when 50% of the users use a typical VoD stream-control function like skip, to view different parts of the video.

Results for Gaussian relay channels typically focus on maximizing transmission rates for given locations of the source, relay, and destination. We introduce an alternative perspective, where the objective is maximizingcoveragefor a given rate. The new objective captures the problem of how to deploy relays to provide a given level of service to a particular geographic area, where the relay locations become a design parameter that can be optimized. We evaluate the decode-and-forward (DF) and compress-and-forward (CF) strategies for the relay channel with respect to the new objective of maximizing coverage. When the objective is maximizing rate, different locations of the destination favor different strategies. When the objective is coverage for a given rate, and the relay is able to decode, DF is uniformly superior in that it provides coverage at any point served by CF. When the channel model is modified to include random fading, we show that the monotone ordering of coverage regions is not always maintained. While the coverage provided by DF is sensitive to changes in the location of the relay and the path loss exponent, CF exhibits a more graceful degradation with respect to such changes. The techniques used to approximate coverage regions are new and may be of independent interest.

We consider a fading version of the dirty-paper problem, as proposed by Grover and Sahai. In this formulation, the various signals involved are complex-valued, and the interference (known only to the transmitter) is multiplied by a random complex-valued coefficient, whose phase is known only to the receiver. We focus on a compound channel formulation, and seek to maximize the worst-case performance. We present an achievable strategy modeled on the lattice-based approach of Erez, Shamai and Zamir and propose heuristic methods to optimize its parameters. We also derive an upper bound on the maximum achievable transmission rates. Our bounds are shown to be tight in some settings, yielding a complete characterization of capacity. We also provide simulation results, indicating the practical effectiveness of our approaches.

In multiuser systems, the downlink capacity to different users is often different due to the near-far effect. We capture this asymmetry in the feedback link by introducing an asymmetric feedback model where different users get different amount of channel feedback from the base-station. Then, we derive the outage probability for the maximum-likelihood receiver, allowing us to study the impact of feedback asymmetry on multiuser performance. Interestingly, we discover that introducing systematic asymmetry in feedback can be beneficial in some cases, where only one user can adapt its power/rate to provide systemwide performance equivalent to that obtained by global feedback to all users.

In this paper, we study the effect of feedback channel noise on the diversity-multiplexing tradeoff in multiuser MIMO systems using quantized feedback, where each user has m transmit antennas and the base-station receiver has n antennas. We derive an achievable tradeoff and use it to show that in SNR-symmetric channels, a single bit of imperfect feedback is sufficient to double the maximum diversity order to 2 mn compared to when there is no feedback (maximum is mn at multiplexing gain of zero). Further, additional feedback bits do not increase this maximum diversity order beyond 2 mn. Finally, the above diversity order gain of mn over non-feedback systems can also be achieved for higher multiplexing gains, albeit requiring more than one bit of feedback.

Channel state feedback at the transmitter is extensively used to increase the reliability of wireless transmissions. In multiuser systems, the downlink capacity to different users is often different due to the near-far effect. We capture this asymmetry by introducing an asymmetric feedback model where different users get a different amount of feedback from the base station. First, we derive the outage probability for the optimum maximum-likelihood receiver which forms an upper bound on the diversity-multiplexing performance. This is accompanied by the conditions under which these bounds can be achieved. Second, we analyze the performance of two popular suboptimal receivers: the spatial decorrelator and the successive interference cancellation receiver. As a special case, when there is no asymmetry, the performance matches feedback-based single-user performance in many scenarios.

This paper describes a fundamental correspondence between Boolean functions and projection operators in Hilbert space. The correspondence is widely applicable, and it is used in this paper to provide a common mathematical framework for the design of both additive and nonadditive quantum error correcting codes. The new framework leads to the construction of a variety of codes including an infinite class of codes that extend the original ((5, 6, 2)) code found by Rains It also extends to operator quantum error correcting codes.

This paper describes a common mathematical framework for the design of additive and non-additive Quantum Error Correcting Codes. It is based on a correspondence between boolean functions and projection operators. The new framework extends to operator quantum error correcting codes.

Results for Gaussian relay channels typically focus on maximizing transmission rates for given locations of the source, relay and destination. We consider an alternative approach, focusing on maximizing coverage for a given rate. This novel perspective enables treatment of the relay location as a design parameter, producing an extra degree of freedom that may be optimized. Focusing on coverage, we evaluate existing approaches, like decode and forward (DF), compress and forward (CF) and compare them with upper bounds. In the process, we obtain some surprising insights on the performance of these approaches.