Reinforcement learning (RL) faces significant challenges in real-world deployments due to the sim-to-real gap, where policies trained in simulators often underperform in practice due to mismatches between training and deployment conditions. Distributionally robust RL addresses this issue by optimizing worst-case performance over an uncertainty set of environments and providing an optimized lower bound on deployment performance. However, existing studies typically assume access to either a generative model or offline datasets with broad coverage of the deployment environment—assumptions that limit their practicality in unknown environments without prior knowledge. In this work, we study the more realistic and challenging setting of online distributionally robust RL, where the agent interacts only with a single unknown training environment while aiming to optimize its worst-case performance. We focus on general f-divergence-based uncertainty sets, including chi-squared and KL divergence balls, and propose a computationally efficient algorithm with sublinear regret guarantees under minimal assumptions. Furthermore, we establish a minimax lower bound on regret of online learning, demonstrating the near-optimality of our approach. Extensive experiments across diverse environments further confirm the robustness and efficiency of our algorithm, validating our theoretical findings.

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.

Planning in non-Markovian environments often requires inferring task structures, such as reward machines, through interactions with the environment. Traditional active grammatical inference methods, like Angluin’s L*algorithm, depend on continuous querying to learn task structures for the underlying planning objectives. In contrast, we propose a hybrid approach that combines passive grammatical inference, using the Regular Positive and Negative Inference (RPNI) algorithm, with online planning. By leveraging pre-collected positive and negative trajectories, RPNI learns a deterministic finite automaton (DFA) that captures the task structure, significantly reducing the need for real-time interactions. Subsequently, online planning is conducted over the product MDP, which integrates the environment with the learned DFA. This hybrid methodology minimizes the cost of online interactions and improves learning efficiency in complex environments. Our approach outperforms baseline algorithms in terms of runtime and sample complexity, and is well-suited for real-world scenarios where task structures are implicit, and interactions with the environment are expensive.

Traditional adversarial attacks typically aim to alter the predicted labels of input images by generating perturbations that are imperceptible to the human eye. However, these approaches often lack explainability. Moreover, most existing work on adversarial attacks focuses on single-stage classifiers, but multi-stage classifiers are largely unexplored. In this paper, we introduce instance-based adversarial attacks for multi-stage classifiers, leveraging Layer-wise Relevance Propagation (LRP), which assigns relevance scores to pixels based on their influence on classification outcomes. Our approach generates explainable adversarial perturbations by utilizing LRP to identify and target key features critical for both coarse and fine-grained classifications. Unlike conventional attacks, our method not only induces misclassification but also enhances the interpretability of the model’s behavior across classification stages, as demonstrated by experimental results.

Offline reinforcement learning (RL) has gained considerable attention for its ability to learn policies from pre-collected data without real-time interaction, which makes it particularly useful for high-risk applications. However, due to its reliance on offline datasets, existing works inevitably introduce assumptions to ensure effective learning, which, however, often lead to a trade-off between robustness to model mismatch and scalability to large environments. In this paper, we enhance both aspects with a novel double-pessimism principle, which conservatively estimates performance and accounts for both limited data and potential model mismatches, two major reasons for the previous trade-off. We then propose a universal, model-free algorithm to learn a policy that is robust to potential environment mismatches, which enhances robustness in a scalable manner. Furthermore, we provide a sample complexity analysis of our algorithm when the mismatch is modeled by the $l_\alpha$-norm, which also theoretically demonstrates the efficiency of our method. Extensive experiments further demonstrate that our approach significantly improves robustness in a more scalable manner than existing methods.

Robust reinforcement learning (RL) under the average reward criterion, which seeks to optimize long-term system performance in uncertain environments, remains a largely unexplored area. To address this challenge, we propose a reduction-based framework that transforms robust average reward optimization into the more extensively studied robust discounted reward optimization by employing a specific discount factor. Our framework provides two key advantages. **Data Efficiency**: We design a model-based reduction algorithm that achieves near-optimal sample complexity, enabling efficient identification of optimal robust policies; **Scalability**: By bypassing the inherent challenges of scaling up average reward optimization, our framework facilitates the design of scalable, convergent algorithms for robust average reward optimization leveraging function approximation. Our algorithmic design, supported by theoretical and empirical analyses, provides a concrete solution to robust average reward RL with the first data efficiency and scalability guarantees, highlighting the framework’s potential to optimize long-term performance under model uncertainty in practical problems.

Transfer reinforcement learning aims to derive a near-optimal policy for a target environment with limited data by leveraging abundant data from related source domains. However, it faces two key challenges: the lack of performance guarantees for the transferred policy, which can lead to undesired actions, and the risk of negative transfer when multiple source domains are involved. We propose a novel framework based on the pessimism principle, which constructs and optimizes a conservative estimation of the target domain’s performance. Our framework effectively addresses the two challenges by providing an optimized lower bound on target performance, ensuring safe and reliable decisions, and by exhibiting monotonic improvement with respect to the quality of the source domains, thereby avoiding negative transfer. We construct two types of conservative estimations, rigorously characterize their effectiveness, and develop efficient distributed algorithms with convergence guarantees. Our framework provides a theoretically sound and practically robust solution for transfer learning in reinforcement learning.

Tensor ring (TR) decomposition demonstrates superior performance in handling high-order tensors. However, traditional TR-based decomposition algorithms face limitations in real-world applications due to large data sizes, missing entries, and outlier corruption. To address these challenges, we propose a scalable and robust TR decomposition algorithm for large-scale tensor data that effectively handles missing entries and gross corruptions. Our method introduces a novel auto-weighted scaled steepest descent approach that adaptively identifies outliers and completes missing entries during decomposition. Additionally, leveraging the tensor ring decomposition model, we develop a Fast Gram Matrix Computation (FGMC) technique and a Randomized Subtensor Sketching (RStS) strategy, significantly reducing storage and computational complexity. Experimental results demonstrate that the proposed method outperforms existing TR decomposition and tensor completion methods.

Domain shift occurs when the data distribution used for testing diverges from the one employed during training, resulting in reduced performance of machine learning models. Domain adaptation (DA) offers techniques to mitigate disparities between two domains and enhance a model’s effectiveness in the target domain. Most existing DA techniques have primarily focused on one-level classifiers (OLC), which are designed for non-hierarchical data. However, there is limited research on DA methods specifically tailored for hierarchical settings featuring a label hierarchy, such as Nested Dichotomies (NDCs) which transform a multiclass classification problem into a series of binary problems. In this paper, we introduce a discriminative domain matching approach tailored for NDCs, which can accommodate labels at various hierarchical levels. Our approach involves the development of an adversarial DA technique aimed at learning an invariant feature representation across the diverse hierarchical levels within the NDC framework. To achieve this, we partition the unlabeled target domain data at different levels of the hierarchy, guided by predicted labels obtained from previous levels. Our experiments on digit datasets demonstrate that our proposed algorithm outperforms the basic NDC model as it achieves higher classification accuracy when applied to data from the target domain.

Robust Markov decision processes (MDPs) aim to find a policy that optimizes the worst-case performance over an uncertainty set of MDPs. Existing studies mostly have focused on the robust MDPs under the discounted reward criterion, leaving the ones under the average-reward criterion largely unexplored. In this paper, we develop the first comprehensive and systematic study of robust average-reward MDPs, where the goal is to optimize the long-term average performance under the worst case. Our contributions are four-folds: (1) we prove the uniform convergence of the robust discounted value function to the robust average-reward function as the discount factor γ goes to 1; (2) we derive the robust average-reward Bellman equation, characterize the structure of its solution set, and prove the equivalence between solving the robust Bellman equation and finding the optimal robust policy; (3) we design robust dynamic programming algorithms, and theoretically characterize their convergence to the optimal policy; and (4) we design two model-free algorithms unitizing the multi-level Monte-Carlo approach, and prove their asymptotic convergence

Tensor completion is the problem of estimating the missing values of high-order data from partially observed entries. Data corruption due to prevailing outliers poses major challenges to traditional tensor completion algorithms, which catalyzed the development of robust algorithms that alleviate the effect of outliers. However, existing robust methods largely presume that the corruption is sparse, which may not hold in practice. In this article, we develop a two-stage robust tensor completion approach to deal with tensor completion of visual data with a large amount of gross corruption. A novel coarse-to-fine framework is proposed which uses a global coarse completion result to guide a local patch refinement process. To efficiently mitigate the effect of a large number of outliers on tensor recovery, we develop a new M-estimator-based robust tensor ring recovery method which can adaptively identify the outliers and alleviate their negative effect in the optimization. The experimental results demonstrate the superior performance of the proposed approach over state-of-the-art robust algorithms for tensor completion.

Automated fault detection and diagnosis systems are critical to safe and efficient operation of smart buildings. A significant amount of building data can be collected and analyzed to detect building component failures. Attacks against such data that are contaminated with small additive disturbances (i.e., adversarial perturbation attacks) could dreadfully impact the performance of such systems while maintaining a high level of imperceptibility. The vulnerability studies of such data attacks is lacking. Specifically, most existing detection and classification models have flat structures, regarded as single-stage classifiers (SSCs), are prone to adversarial data perturbation attacks. In this article, we present a coarse-to-fine hierarchical fault detection and multilevel diagnosis (HFDD) model, and formulate a mathematical program to derive targeted attacks on the model with respect to a prespecified target diagnosis level. Two algorithms are developed based on convex relaxations of the formulated program for nontargeted attacks. An alternating direction method of multipliers-based solver is developed for the convex programs. Extensive experiments are conducted using two real-world datasets of measurements from air handling units and chillers, demonstrating the feasibility of the proposed attacks with regard to misclassification rate and imperceptibility of the attack. We also show that the HFDD is more robust to disturbances than SSC-based fault detection and multilevel diagnosis systems.

The goal of tensor completion is to recover a tensor from a subset of its entries, often by exploiting its low-rank property. Among several useful definitions of tensor rank, the low tubal rank was shown to give a valuable characterization of the inherent low-rank structure of a tensor. While some low-tubal-rank tensor completion algorithms with favorable performance have been recently proposed, these algorithms utilize second-order statistics to measure the error residual, which may not work well when the observed entries contain large outliers. In this article, we propose a new objective function for low-tubal-rank tensor completion, which uses correntropy as the error measure to mitigate the effect of the outliers. To efficiently optimize the proposed objective, we leverage a half-quadratic minimization technique whereby the optimization is transformed to a weighted low-tubal-rank tensor factorization problem. Subsequently, we propose two simple and efficient algorithms to obtain the solution and provide their convergence and complexity analysis. Numerical results using both synthetic and real data demonstrate the robust and superior performance of the proposed algorithms.

In robust Markov decision processes (MDPs), the uncertainty in the transition kernel is addressed by finding a policy that optimizes the worst-case performance over an uncertainty set of MDPs. While much of the literature has focused on discounted MDPs, robust average-reward MDPs remain largely unexplored. In this paper, we focus on robust average-reward MDPs, where the goal is to find a policy that optimizes the worst-case average reward over an uncertainty set. We first take an approach that approximates average-reward MDPs using discounted MDPs. We prove that the robust discounted value function converges to the robust average-reward as the discount factor goes to 1, and moreover when it is large, any optimal policy of the robust discounted MDP is also an optimal policy of the robust average-reward. We further design a robust dynamic programming approach, and theoretically characterize its convergence to the optimum. Then, we investigate robust average-reward MDPs directly without using discounted MDPs as an intermediate step. We derive the robust Bellman equation for robust average-reward MDPs, prove that the optimal policy can be derived from its solution, and further design a robust relative value iteration algorithm that provably finds its solution, or equivalently, the optimal robust policy.

Robust tensor completion aims to recover a tensor from partially observed noisy entries that may be contaminated with large outliers by exploiting its low-rank property. While there exist several robust tensor completion algorithms, their reliance on singular value decomposition (SVD) limits their scalability. In this paper, we propose a new robust and parallelizable tensor completion method using the tubal rank model. The proposed method rests on tensor factorization, thus averts the costly SVD iterations, and leverages a differentiable, robust correntropy error measure to mitigate the effect of outliers. Leveraging a half-quadratic technique and an alternating steepest descent method, we develop a new SVD-free and parallelizable robust tensor completion algorithm. Numerical results using both synthetic and real data demonstrate the robustness and efficiency of the proposed algorithm.

Robust Markov decision processes (MDPs) address the challenge of model uncertainty by optimizing the worst-case performance over an uncertainty set of MDPs. In this paper, we focus on the robust average-reward MDPs under the model-free setting. We first theoretically characterize the structure of solutions to the robust average-reward Bellman equation, which is essential for our later convergence analysis. We then design two model-free algorithms, robust relative value iteration (RVI) TD and robust RVI Q-learning, and theoretically prove their convergence to the optimal solution. We provide several widely used uncertainty sets as examples, including those defined by the contamination model, total variation, Chi-squared divergence, Kullback-Leibler (KL) divergence, and Wasserstein distance.

The evaluation of classifiers' robustness against adversarial attacks is typically performed through metrics based on the minimal perturbation required for misclassification. The conventional method of generating these perturbations relies on setting a limit on the maximum allowed perturbation (restricted attack method) and a non-targeted attack formulation. This approach, however, disregards any relationships between classes. Our paper introduces a novel, non-targeted, bound-restricted method for achieving coarse misclassification, so that the perturbed feature is classified outside its true coarse class. We present an efficient, single-step solution to the coarse misclassification problem and analyze its computational requirements. Our experiments showcase the superiority of our method, surpassing state-of-the-art in terms of both the perceptibility of adversarial examples and runtime.

Tensor ring (TR) decomposition has recently received increased attention due to its superior expressive performance for high-order tensors. However, the applicability of traditional TR decomposition algorithms to real-world applications is hindered by prevalent large data sizes, missing entries, and corruption with outliers. In this work, we propose a scalable and robust TR decomposition algorithm capable of handling large-scale tensor data with missing entries and gross corruptions. We first develop a novel auto-weighted steepest descent method that can adaptively fill the missing entries and identify the outliers during the decomposition process. Further, taking advantage of the tensor ring model, we develop a novel fast Gram matrix computation (FGMC) approach and a randomized subtensor sketching (RStS) strategy which yield significant reduction in storage and computational complexity. Experimental results demonstrate that the proposed method outperforms existing TR decomposition methods in the presence of outliers, and runs significantly faster than existing robust tensor completion algorithms.

Traditional subspace clustering aims to cluster data lying in a union of linear subspaces. The vectorization of high-dimensional data to 1-D vectors to perform clustering ignores much of the structure intrinsic to such data. To preserve said structure, in this work we exploit clustering in a high-order tensor space rather than a vector space. We develop a novel low-tensor-rank representation (LTRR) for unfolded matrices of tensor data lying in a low-rank tensor space. The representation coefficient matrix of an unfolding matrix is tensorized to a 3-order tensor, and the low-tensor-rank constraint is imposed on the transformed coefficient tensor to exploit the self-expressiveness property. Then, inspired by the multi-view clustering framework, we develop a multi-mode tensor space clustering algorithm (MMTSC) that can deal with tensor space clustering with or without missing entries. The tensor is unfolded along each mode, and the coefficient matrices are obtained for each unfolded matrix. The low tensor rank constraint is imposed on a tensor combined from transformed coefficient tensors of each mode, such that the proposed method can simultaneously capture the low rank property for the data within each tensor space and maintain cluster consistency across different modes. Experimental results demonstrate that the proposed MMTSC algorithm can outperform existing clustering algorithms in many cases.

Adversarial attacks can drastically reduce the accuracy and confidence level of classifiers while being imperceptible. Existing studies on the topic have largely focused on one-stage classifiers. In this paper, we study the robustness of two Two-Stage Hierarchical Classifier models, the flat and top-down hierarchical classifiers, termed FHC and TDHC respectively, to targeted and confidence reduction attacks. We formulate feasibility programs based on similarity and distance measures for the one-shot synthesis of adversarial examples, and devise a generative approach to the solution. In this approach, the adjustable parameters of a generative network are iteratively updated by optimizing loss functions for the dual objective of (i) low attack perceptibility and (ii) small distance from desired soft predictions. We demonstrate the performance of the proposed approach in terms of imperceptibilty and measures of attack success, and show it compares favorably with state-of-the-art techniques.

Tensor completion aims to recover the missing entries of a partially observed tensor by exploiting its low-rank structure, and has been applied to visual data recovery. In applications where the data arrives sequentially such as streaming video completion, the missing entries of the tensor need to be dynamically recovered in a streaming fashion. Traditional streaming tensor completion algorithms treat the entire visual data as a tensor, which may not work satisfactorily when there is a big change in the tensor subspace along the temporal dimension, such as due to strong motion across the video frames. In this paper, we develop a novel patch tracking-based streaming tensor ring completion framework for visual data recovery. Given a newly incoming frame, small patches are tracked from the previous frame. Meanwhile, for each tracked patch, a patch tensor is constructed by stacking similar patches from the new frame. Patch tensors are then completed using a streaming tensor ring completion algorithm, and the incoming frame is recovered using the completed patch tensors. We propose a new patch tracking strategy that can accurately and efficiently track the patches with missing data. Further, a new streaming tensor ring completion algorithm is proposed which can efficiently and accurately update the latent core tensors and complete the missing entries of the patch tensors. Extensive experimental results demonstrate the superior performance of the proposed algorithms compared with both batch and streaming state-of-the-art tensor completion methods.

The problem of representative selection amounts to sampling few informative exemplars from large datasets. Existing approaches to data selection often fall short of simultaneously handling non-linear data structures, sampling concise and non-redundant subsets, rejecting outliers, and yielding interpretable outcomes. This paper presents a novel representative selection approach, dubbed MOSAIC, for drawing descriptive sketches of arbitrary manifold structures. Resting upon a novel quadratic formulation, MOSAIC advances a multi-criteria selection approach that maximizes the global representation power of the sampled subset, ensures novelty of the samples by minimizing redundancy, and rejects disruptive information by effectively detecting outliers. Theoretical analyses shed light on geometrical characterization of the obtained sketch and reveal that the sampled representatives maximize a well-defined notion of data coverage in a transformed space. In addition, we present a highly scalable randomized implementation of the proposed algorithm shown to bring about substantial speedups. MOSAIC’s superiority in achieving the desired characteristics of a representative subset all at once while exhibiting remarkable robustness to various outlier types is demonstrated via extensive experiments conducted on both real and synthetic data with comparisons to state-of-the-art algorithms.

Reinforcement learning and planning have been revolutionized in recent years, due in part to the mass adoption of deep convolutional neural networks and the resurgence of powerful methods to refine decision-making policies. However, the problem of sparse reward signals and their representation remains pervasive in many domains. While various rewardshaping mechanisms and imitation learning approaches have been proposed to mitigate this problem, the use of humanaided artificial rewards introduces human error, sub-optimal behavior, and a greater propensity for reward hacking. In this paper, we mitigate this by representing objectives as automata in order to define novel reward shaping functions over this structured representation. In doing so, we address the sparse rewards problem within a novel implementation of Monte Carlo Tree Search (MCTS) by proposing a reward shaping function which is updated dynamically to capture statistics on the utility of each automaton transition as it pertains to satisfying the goal of the agent. We further demonstrate that such automaton-guided reward shaping can be utilized to facilitate transfer learning between different environments when the objective is the same.

Adversarial attacks have exposed the vulnerability of one-stage classifiers to carefully crafted perturbations which were shown to drastically alter their predictions while remaining imperceptible. In this paper, we examine the susceptibility of coarse-to-fine hierarchical classifiers to such types of attacks. We formulate convex programs to generate perturbations attacking these models and propose a generic solution based on the Alternating Direction Method of Multipliers (ADMM). We evaluate the performance of the proposed models using the degradation in classification accuracy and imperceptibility measures in comparison to perturbations generated to fool one-stage classifiers.

Adversarial attacks were shown to drastically degrade the performance of one-stage classifiers while being undetectable. In this paper, we examine the susceptibility of both flat and top-down hierarchical classifiers, abbreviated FHCs and TDHCs respectively, to targeted adversarial attacks. Convex programs are formulated to generate input perturbations geared at altering their output predictions according to pre-specified targets (e.g., changing the prediction of a ‘cat’ to a ‘car’ rather than a ‘dog’ or some other pet). A competitive solver based on the Alternating Direction Method of Multipliers (ADMM) is developed and is shown to outperform state-of-the-art solvers. The attacks developed for FHCs and TDHCs are evaluated based on their success rate and imperceptibility. It is shown that FHCs are inherently more robust than TDHCs to said attacks in the sense that fooling their coarse classification generally requires higher levels of perturbation.

Periodic signals admit sparse representations in nested periodic dictionaries (NPDs). While sparse recovery algorithms rooted in the theory of compressive sensing can successfully recover their underlying periods, existing recovery conditions derived for random dictionaries are of limited use in this context as they fail to explain the achievability results of said algorithms. In addition, provable achievability guarantees specific to NPDs have been heretofore lacking. In this paper, we derive exact recovery conditions for sparse periodic signals by leveraging prior information about the structure of NPDs. As instances of such dictionaries, we investigate the achievability conditions for the Farey and the Ramanujan Periodicity Transform dictionaries. Our numerical results demonstrate that the newly derived conditions can provide guarantees for exact recovery with the Farey dictionary, and in turn for exact period estimation, for large enough data lengths.

The planning domain has experienced increased interest in the formal synthesis of decision-making policies. This formal synthesis typically entails finding a policy which satisfies formal specifications in the form of some well-defined logic. While many such logics have been proposed with varying degrees of expressiveness and complexity in their capacity to capture desirable agent behavior, their value is limited when deriving decision-making policies which satisfy certain types of asymptotic behavior in general system models. In particular, we are interested in specifying constraints on the steady-state behavior of an agent, which captures the proportion of time an agent spends in each state as it interacts for an indefinite period of time with its environment. This is sometimes called the average or expected behavior of the agent and the associated planning problem is faced with significant challenges unless strong restrictions are imposed on the underlying model in terms of the connectivity of its graph structure. In this paper, we explore this steady-state planning problem that consists of deriving a decision-making policy for an agent such that constraints on its steady-state behavior are satisfied. A linear programming solution for the general case of multichain Markov Decision Processes (MDPs) is proposed and we prove that optimal solutions to the proposed programs yield stationary policies with rigorous guarantees of behavior.

In a multi-tenant cloud, a number of Virtual Machines (VMs) are collocated on the same physical machine to optimize performance, power consumption and maximize profit. This, however, increases the risk of a malicious VM performing side-channel attacks and leaking sensitive information from neighboring VMs. As such, this paper develops and analyzes a game-theoretic framework for the VM migration timing problem in which the cloud provider decideswhento migrate a VM to a different physical machine to reduce the risk of being compromised by a collocated malicious VM. The adversary decides the rate at which she launches new VMs to collocate with the victim VMs. Our formulation captures a data leakage model in which the cost incurred by the cloud provider depends on the duration of collocation with malicious VMs. It also captures costs incurred by the adversary in launching new VMs and by the defender in migrating VMs. We establish sufficient conditions for the existence of Nash equilibria for general cost functions, as well as for specific instantiations, and characterize the best response for both players. Furthermore, we extend our model to characterize its impact on the attacker’s payoff when the cloud utilizes intrusion detection systems that detect side-channel attacks. Our theoretical findings are corroborated with extensive numerical results in various settings as well as a proof-of-concept implementation in a realistic cloud setting.

This paper proposes a sketch-based approach to the community detection problem which clusters the full graph through the use of an informative and concise sketch. The reduced sketch is built through an effective sampling approach which selects few nodes that best represent the complete graph and operates on a pairwise node similarity measure based on the average commute time. After sampling, the proposed algorithm clusters the nodes in the sketch, and then infers the cluster membership of the remaining nodes in the full graph based on their aggregate similarity to nodes in the partitioned sketch. By sampling nodes with strong representation power, our approach can improve the success rates over full graph clustering. In challenging cases with large node degree variation, our approach not only maintains competitive accuracy with full graph clustering despite using a small sketch, but also outperforms existing sampling methods. The use of a small sketch allows considerable storage savings, and computational and timing improvements for further analysis such as clustering and visualization. We provide numerical results on synthetic data based on the homogeneous, heterogeneous and degree corrected versions of the stochastic block model, as well as experimental results on real-world data.

The formal synthesis of automated or autonomous agents has elicited strong interest from the artificial intelligence community in recent years. This problem space broadly entails the derivation of decision-making policies for agents acting in an environment such that a formal specification of behavior is satisfied. Popular formalisms for such specifications include the quintessential Linear Temporal Logic (LTL) and Computation Tree Logic (CTL) which reason over infinite sequences and trees, respectively, of states. However, the related and relevant problem of reasoning over the frequency with which states are visited infinitely and enforcing behavioral specifications on the same has received little attention. That problem, known as Steady-State Policy Synthesis (SSPS) or steady-state control, is the focus of this paper. Prior related work has been mostly confined to unichain Markov Decision Processes (MDPs), while a tractable solution to the general multichain setting heretofore remains elusive. In this paper, we provide a solution to the latter within the context of multichain MDPs over a class of policies that account for all possible transitions in the given MDP. The solution policy is derived from a novel linear program (LP) that encodes constraints on the limiting distributions of the Markov chain induced by said policy. We establish a one-to-one correspondence between the feasible solutions of the LP and the stationary distributions of the induced Markov chains. The derived policy is shown to maximize the reward among the constrained class of stationary policies and to satisfy the specification constraints even when it does not exercise all possible transitions.

Existing work on adversarial attacks on classification tasks has focused on classifiers that make use of simple hypothesis testing models. In this work, we study the vulnerability of composite classifiers employing generalized likelihood ratio tests to adversarial perturbation attacks. We derive imperceptible adversarial attacks for a multiple composite hypothesis testing setting using gradient methods. The work considers scenarios where the attacker has access to the ground truth class. The classification performance, with and without perturbation, is characterized based on the notions of posterior sensitivity and specificity.

This letter presents an effective and simple method, termed Global Conformity Pursuit (GCP), for robust manifold learning. Data points lying on a union of low-dimensional nonlinear manifolds are expected to be highly conforming. On the other hand, outliers do not typically adhere to low-dimensional structures or otherwise do not exist in large numbers. Hence, they can be identified by their low overall resemblance to the rest of the data. Our kernel-based setting allows us to capture the underlying nonlinear structure of the manifold data, while avoiding the construction of local neighborhood regions which typically causes extreme sensitivity to noise and outliers. Aside from its significantly simple structure-involving only a matrix evaluation and multiplication-GCP is the first manifold learning approach that is simultaneously noniterative and capable of tolerating a large number of outliers, dependent outliers, and noise components. Theoretical analysis guarantees a large gap between conformity values of inliers and outliers. Experimental results showcase potential uses of the proposed framework on benchmark datasets.

We consider the non-line-of-sight (NLOS) imaging of an object using the light reflected off a diffusive wall. The wall scatters incident light such that a lens is no longer useful to form an image. Instead, we exploit the 4D spatial coherence function to reconstruct a 2D projection of the obscured object. The approach is completely passive in the sense that no control over the light illuminating the object is assumed and is compatible with the partially coherent fields ubiquitous in both the indoor and outdoor environments. We formulate a multi-criteria convex optimization problem for reconstruction, which fuses the reflected field's intensity and spatial coherence information at different scales. Our formulation leverages established optics models of light propagation and scattering and exploits the sparsity common to many images in different bases. We also develop an algorithm based on the alternating direction method of multipliers to efficiently solve the convex program proposed. A means for analyzing the null space of the measurement matrices is provided as well as a means for weighting the contribution of individual measurements to the reconstruction. This paper holds promise to advance passive imaging in the challenging NLOS regimes in which the intensity does not necessarily retain distinguishable features and provides a framework for multi-modal information fusion for efficient scene reconstruction.

We present a novel game-theoretic framework for the Virtual Machine (VM) migration timing problem. In a multi-tenant cloud, a number of VMs are collocated on the same physical machine. This increases the risk of a malicious VM performing side-channel attacks and leaking sensitive information. To this end, this paper develops and analyzes a game-theoretic framework for the timing problem in which the cloud provider decides when to migrate a VM to a different physical machine to reduce the risk of being compromised by a collocated malicious VM. The adversary decides the rate at which she launches new VMs to collocate with the victim VMs. Our formulation captures a data leakage model in which the cost incurred by the cloud provider depends on the duration of collocation as well as the overhead in migration. We establish sufficient conditions for the existence of Nash equilibria for general cost functions, as well as for specific instantiations, and characterize the best response for both players. Our theoretical findings are corroborated with extensive numerical results in various settings.

This paper focuses on the low rank plus sparse matrix decomposition problem in big data settings. Conventional algorithms solve high-dimensional optimization problems that scale with the data dimension, which limits their scalability. In addition, existing randomized approaches mostly rely on blind random sampling. In this paper, the drawbacks of random sampling from coherent/structured data matrices are analyzed showing that random sampling cannot provide efficient descriptive sketches of coherent data. In addition, a column/row subspace pursuit algorithm which recovers the low rank component via a small set of informative columns/rows of the data is proposed. The obtained column and row spaces are updated in each iteration to converge to the column and row spaces of the low rank matrix. The informative columns are located using the information embedded in the row space while the informative rows are identified using the information embedded in the column space.

Repetitive visual stimuli induce periodic Visual Evoked Potentials (VEPs) in the brain that can be potentially identified in an EEG trace. The ability to distinguish frequencies and patterns due to different stimuli is the basis for brain computer interfaces (BCIs) used for communication and control of neurologically disabled patients. Since such responses are recorded in presence of high levels of noise from background brain processes, the detection task is rather challenging. In this work, we propose a detection approach for VEPs based on Ramanujan Periodicity Transform matrices (RPT), which have shown promise in detecting periodicities in data. Our results show that the RPT-based approach can outperform conventional spectral techniques and the state-of-the-art correlation analysis, and is more compatible with real-time BCIs which have to work with short duration EEG epochs. The proposed approach is fairly robust to unknown natural latencies in brain response.

Videos of complex events are difficult to represent solely as bags of low level features. Increasingly, supervised concepts or attributes are being employed as the intermediate representation of such videos. We propose a probabilistic framework that models the conditional relationships between the concepts and events and devise an approximate yet tractable solution to infer the posterior distribution to perform event classification. Using noisy outputs of pre-trained concept detectors, we learn semantic and visual dependencies between event and concept pairs. The co-occurrence between concept pairs is also learned as a marginal over training samples. The proposed method then employs the learned prior, as well as the probabilities of occurrence of specific concepts in a test video to infer the probability of each event using weighted average one-dependence estimation. The evaluation shows that our method improves event classification compared to recent literature on the TRECVID data set.

This paper presents a remarkably simple, yet powerful, algorithm for robust Principal Component Analysis (PCA). In the proposed approach, an outlier is set apart from an inlier by comparing their coherence with the rest of the data points. As inliers lie on a low dimensional subspace, they are likely to have strong mutual coherence provided there are enough inliers. By contrast, outliers do not typically admit low dimensional structures, wherefore an outlier is unlikely to bear strong resemblance with a large number of data points. The mutual coherences are computed by forming the Gram matrix of normalized data points. Subsequently, the subspace is recovered from the span of a small subset of the data points that exhibit strong coherence with the rest of the data. As coherence pursuit only involves one simple matrix multiplication, it is significantly faster than the state of-the-art robust PCA algorithms. We provide a mathematical analysis of the proposed algorithm under a random model for the distribution of the inliers and outliers. It is shown that the proposed method can recover the correct subspace even if the data is predominantly outliers. To the best of our knowledge, this is the first provable robust PCA algorithm that is simultaneously non-iterative, can tolerate a large number of outliers and is robust to linearly dependent outliers.

This paper presents a new scalable approach, termed Innovation Pursuit (iPursuit), to the problem of subspace clustering. iPursuit rests on a new geometrical idea whereby each subspace is identified based on its novelty with respect to the other subspaces. The subspaces are identified consecutively by solving a series of simple linear optimization problems, each searching for a direction of innovation in the span of the data. A detailed mathematical analysis is provided establishing sufficient conditions for the proposed approach to correctly cluster the data points. Moreover, the proposed direction search approach can be integrated with spectral clustering to yield a new variant of spectral-clustering-based algorithms. Remarkably, the proposed approach can provably yield exact clustering even when the subspaces have significant intersections. The numerical simulations demonstrate that iPursuit can often outperform the state-of-the-art subspace clustering algorithms – more so for subspaces with significant intersections – along with substantial reductions in computational complexity.

Random column sampling is not guaranteed to yield data sketches that preserve the underlying structures of the data and may not sample sufficiently from less-populated data clusters. Also, adaptive sampling can often provide accurate low rank approximations, yet may fall short of producing descriptive data sketches, especially when the cluster centers are linearly dependent. Motivated by that, this letter introduces a novel randomized column sampling tool dubbed spatial random sampling (SRS), in which data points are sampled based on their proximity to randomly sampled points on the unit sphere. The most compelling feature of SRS is that the corresponding probability of sampling from a given data cluster is proportional to the surface area the cluster occupies on the unit sphere, independently of the size of the cluster population. Although it is fully randomized, SRS is shown to provide descriptive and balanced data representations. The proposed idea addresses a pressing need in data science and holds potential to inspire many novel approaches for analysis of big data.

This letter presents a new spectral-clustering-based approach to the subspace clustering problem. Underpinning the proposed method is a convex program for optimal direction search, which for each data point d finds an optimal direction in the span of the data that has minimum projection on the other data points and nonvanishing projection on d. The obtained directions are subsequently leveraged to identify a neighborhood set for each data point. An alternating direction method of multipliers framework is provided to efficiently solve for the optimal directions. The proposed method is shown to often outperform the existing subspace clustering methods, particularly for unwieldy scenarios involving high levels of noise and close subspaces, and yields the state-ofthe-art results for the problem of face clustering using subspace segmentation.

We derive fundamental sample complexity bounds for recovering sparse and structured signals for linear and nonlinear observation models, including sparse regression, group testing, multivariate regression, and problems with missing features. In general, sparse signal processing problems can be characterized in terms of the following Markovian property. We are given a set of N variables X1,X2,...,XN, and there is an unknown subset of variables S ⊂ {1,...,N} that are relevant for predicting outcomes Y. More specifically, when Y is conditioned on {Xn}n∈S, it is conditionally independent of the other variables, {Xn}n∉S. Our goal is to identify the set S from samples of the variables X and the associated outcomes Y. We characterize this problem as a version of the noisy channel coding problem. Using asymptotic information theoretic analyses, we establish mutual information formulas that provide sufficient and necessary conditions on the number of samples required to successfully recover the salient variables. These mutual information expressions unify conditions for both linear and nonlinear observations. We then compute sample complexity bounds for the aforementioned models, based on the mutual information expressions in order to demonstrate the applicability and flexibility of our results in general sparse signal processing models.

As wireless networks continue to grow rapidly denser with the introduction of various wireless-enabled elements, signal interference coupled with limited radio spectrum availability emerges as a significant hindrance to network performance. In order to retain high network throughput, channels must be strategically assigned to nodes in a way that minimizes signal overlap between neighboring nodes. Current static channel assignment techniques are intolerant of network variations and growth, but flexible dynamic techniques are becoming more feasible with the introduction of software defined networks and network function virtualization. As network maintenance tasks are increasingly handled by software, however, network stability becomes susceptible to malicious behavior. In this paper, we adopt an attacker's prespective and expose stealthy attacks - which we coin “pinball” Attacks - that aim to trigger unnecessary channel switching behavior in a network and increase signal interference between neighboring nodes. We develop a Markov Decision Process (MDP) framework and investigate suboptimal attack policies applied to a number of real-world topologies. We derive attack policies as approximate MDP solutions due to the exponentially large state space. Our results show that pinball attack outperforms other attack policies such as Denial of Service, Random, and other heuristic policies.

This paper presents a new randomized approach to high-dimensional low rank (LR) plus sparse matrix decomposition. For a data matrix D ∈R^N_1 \times N_2, the complexity of conventional decomposition methods is O(N_1 N_2 r), which limits their usefulness in big data settings (r is the rank of the LR component). In addition, the existing randomized approaches rely for the most part on uniform random sampling, which may be inefficient for many real world data matrices. The proposed subspace learning based approach recovers the LR component using only a small subset of the columns/rows of data and reduces complexity to O(\max(N_1,N_2) r^2). Even when the columns/rows are sampled uniformly at random, the sufficient number of sampled columns/rows is shown to be roughly O(r μ), where μis the coherency parameter of the LR component. In addition, efficient sampling algorithms are proposed to address the problem of column/row sampling from structured data.

Quickest change point detection is concerned with the detection of statistical change(s) in sequences while minimizing the detection delay subject to false alarm constraints. In this letter, the problem of change point detection is studied when the decision maker only has access to compressive measurements. First, an expression for the average detection delay of Shiryaev’s procedure with compressive measurements is derived in the asymptotic regime where the probability of false alarm goes to zero. Second, the dependence of the delay on the compression ratio and the signal to noise ratio is explicitly quantified. The ratio of delays with and without compression is studied under various sensing matrix constructions, including Gaussian ensembles and random projections. For a target delay ratio, a sufficient condition on the number of measurements required to meet this objective with prespecified probability is derived.

A correction of Lemma III. in the above-named work is presented.

In traditional sparse recovery problems, the goal is to identify the support of compressible signals using a small number of measurements. In contrast, in this paper the problem of identification of a sparse number of statistical changes in stochastic phenomena is considered. This framework, which is newly introduced herein, is termed Compressed Change Detection. In particular, given a large number N of features, the goal is to detect a small set of features that undergoes a statistical change using a small number of measurements. The main approach relies on integrating ideas from the theory of identifying codes with change point detection in sequential analysis. If the stochastic properties of certain features change, then the changes can be detected by examining the covering set of an identifying code. Sufficient conditions are derived for the probability of detection to approach 1 in the asymptotic regime where N is large. Several applications and generalizations of the proposed framework are presented.

Strong impossibility results for noisy group testing are derived. It is shown that regardless of the allowed error probability in identifying the defective set, the required of number of measurements is almost the same as that required for the error probability to be arbitrarily small. Our proof technique involves the use of the blowing-up lemma.

This letter derives strong impossibility results for several sparse signal processing problems. It is shown that regardless of the allowed error probability in identifying the salient support set (as long as this probability is below one), the required number of measurements is almost the same as that required for the error probability to be arbitrarily small. Our proof technique involves the use of the blowing-up lemma and can be applied to diverse problems from noisy group testing to graphical model selection as long as the observations are discrete.

In this work we investigate the sample complexity of support recovery in sparse signal processing models, with special focus on two compressive sensing scenarios. In particular, we consider models where N covariates X = (X1,...,XN) along with outcome Y are observed, with the assumption that the outcome Y is conditionally independent of the other covariates given K ≪ N covariates. Using asymptotic information theoretic analyses, we establish sufficient conditions on the number of samples in order to successfully recover the K salient covariates. We apply our results to two variants of the compressive sensing (CS) problem: (1) compressive sensing with a measurement noise model, (2) 1-bit quantized compressive sensing. In both models we consider sensing with independent and correlated Gaussian sensing matrices. We show that the sufficiency bounds we obtain on the number of measurements in both cases are comparable to the best known bounds while providing a novel perspective for the theoretical analysis of such models. In addition, we quantify how the correlation between the sensing columns affects the number of measurements. Our findings for the CS models demonstrate the applicability and flexibility of our general results on the sample complexity in sparse signal processing models.

The problem of classifying graphs with respect to connectivity via partial observations of nodes is posed as a composite hypothesis testing problem with controlled sensing. An observation at a node is a subset of edges incident to the node on the complete graph drawn according to a probability model, which are modeled as conditionally independent given their neighborhoods. Connectivity is measured through average node degree and is classified with respect to a threshold. A simple approximation of the controlled sensing test is derived and simulated on Erdös-Rènyi Model A graphs to characterize error probabilities as a function of expected stopping times. It is shown that the proposed test achieves favorable tradeoffs between the classification error and the number of measurements and further outperforms existing approaches, especially at low target error rates. Furthermore, the proposed test achieves asymptotically optimal error performance, as the error rate goes to zero.

In this work we derive fundamental limits for many linear and non-linear sparse signal processing models including group testing, quantized compressive sensing, multivariate regression and observations with missing features. In general, sparse signal processing problems can be characterized in terms of the following Markovian property. We are given a set of N variables X1, X2, ..., XN, and there is an unknown subset of variables S ⊂ {1, 2, ..., N} that are relevant for predicting outcomes/outputs Y. In other words, when Y is conditioned on {Xn}nϵSit is conditionally independent of the other variables, {Xn}n∉S. Our goal is to identify the set S from samples of the variables X and the associated outcomes Y. We characterize this problem as a version of the noisy channel coding problem. Using asymptotic information theoretic analyses, we establish mutual information formulas that provide sufficient and necessary conditions on the number of samples required to successfully recover the salient variables. These mutual information expressions unify conditions for both linear and non-linear observations. We then compute sample complexity bounds for the aforementioned models, based on the mutual information expressions.

Recent advances in wireless technologies have enabled many new applications in Intelligent Transportation Systems (ITS) such as collision avoidance, cooperative driving, congestion avoidance, and traffic optimization. Due to the vulnerable nature of wireless communication against interference and intentional jamming, ITS face new challenges to ensure the reliability and the safety of the overall system. In this paper, we expose a class of stealthy attacks -- Stuck in Traffic (SiT) attacks -- that aim to cause congestion by exploiting how drivers make decisions based on smart traffic signs. An attacker mounting a SiT attack solves a Markov Decision Process problem to find optimal/suboptimal attack policies in which he/she interferes with a well-chosen subset of signals that are based on the state of the system. We apply approximate policy iteration algorithms to derive potent attack policies. We evaluate their performance on a number of systems and compare them to other attack policies including random, myopic and DoS attack policies. The generated policies, albeit suboptimal, are shown to significantly outperform other attack policies as they maximize the expected cumulative reward from the standpoint of the attacker.

In this paper, the problem of multiple hypothesis testing with observation control is considered. The structure of the optimal controller under various asymptotic regimes is studied. First, a setup with a fixed sample size is considered. In this setup, the asymptotic quantity of interest is the optimal exponent for the maximal error probability. For the case of binary hypothesis testing, it is shown that the optimal error exponent corresponds to the maximum Chernoff information over the choice of controls. It is also shown that a pure stationary control policy, i.e., a fixed policy which does not depend on specific realizations of past measurements and past controls (open-loop), is asymptotically optimal even among the class of all causal control policies. We also derive lower and upper bounds for the optimal error exponent for the case of multiple hypothesis testing. Second, a sequential setup is considered wherein the controller can also decide when to stop taking observations. In this case, the objective is to minimize the expected stopping time subject to the constraints of vanishing error probabilities under each hypothesis. A sequential test is proposed for testing multiple hypotheses and is shown to be asymptotically optimal.

The problem of controlled sensing for multihypothesis testing is considered. Prior to decision making, a controller sequentially chooses among a set of control actions to shape the quality of the observations. The goal is to design an efficient control policy, a stopping rule and a final decision rule, to minimize the expected stopping time subject to hard constraints on the risks associated with wrong decisions about each hypothesis. We propose a sequential test, which is shown to be asymptotically optimal when the risks are sufficiently small. Optimality is based on a derived lower bound on the minimum expected stopping time of tests in the class of tests satisfying the predefined risk constraints. Furthermore, by viewing the variable-length coding problem as a special case of sequential multihypothesis testing with observation control, we recover the classic result of Burnašev on the expected coding length for variable-length coding over Discrete Memoryless Channels (DMCs) at zero rate.

The fundamental task of group testing is to recover a small distinguished subset of items from a large population while efficiently reducing the total number of tests (measurements). The key contribution of this paper is in adopting a new information-theoretic perspective on group testing problems. We formulate the group testing problem as a channel coding/decoding problem and derive a single-letter characterization for the total number of tests used to identify the defective set. Although the focus of this paper is primarily on group testing, our main result is generally applicable to other compressive sensing models.

A crucial task for a network of cognitive radios is to detect occupied frequency bands, to protect transmissions of primary users, and to identify spectrum holes to maximize the utilization of wasted resources. This paper is motivated by the need to account for challenging constraints that naturally arise in such applications such as channel model uncertainties and demanding sensitivity constraints of the sensing devices. We propose false discovery rate (FDR) based cooperative strategies to sense the occupancy of the spectrum. The strategies we propose could either be used to maximize bandwidth utilization or to provide guarantees on incurred interference levels. The proposed strategies are robust to significant uncertainties such as lack of CSI, fading and shadowing effects. The key idea of the paper is that the twin objectives of bandwidth utilization and interference control can significantly benefit from group testing across all channels in contrast to conventionally employed channel-by-channel detection strategy. Furthermore, it is shown that the cooperative sensing strategy significantly reduces sensitivity requirements. We quantify the effect of channel occupancy rate on the required cooperation degree for achieving a guaranteed level of primary user protection.

We consider relay cooperation with imperfect channel state information (CSI) in the downlink of wireless networks. In particular, we consider a two-phase transmission where in the first phase the base station broadcasts information to the relays; the relays decode the data fully or partially depending on the transmission rate and the quality of their corresponding communication links. During the second phase, the relays cooperate by jointly beamforming information to multiple users given that channel mean and covariance are available at the transmitter side. The goal is to optimize the total network throughput (taking into account both transmission phases) by proper choice of the transmission rates, cooperation architecture and beamforming transmit vectors from the relays. The key contribution of this paper lies in the consideration of the impact of CSI imperfections in such a system. We first formulate the problem of finding the optimum throughput, which is not amenable to analytical solution. We therefore derive a suboptimum adaptive beamforming strategy that maximizes a derived upper bound on the average system throughput. Even though the relays have imperfect CSI, it is shown that relay cooperation can significantly improve the overall system throughput.

This correspondence deals with the outage capacity of relay networks in the low signal-to-noise ratio (SNR) regime. This work is motivated by the fact that in relay channels, unlike multi-antenna point-to-point links, the transmitters, i.e., source and relays, may not be co-located and therefore their channel statistics can be quite different. It has been recently shown that bursty amplify and forward (BAF) is outage optimal when all the links have a Rayleigh distribution. In this correspondence, it is shown that BAF is in fact outage optimal for a wide class of independent channels with smooth distribution functions. Optimality of BAF is further generalized to a special class of dependent channels, namely, the case where we opportunistically use only the best relay (out of N relays). It turns out that relative to the strategy where all the N relays are used, this opportunistic best relay strategy uses significantly smaller average power (independent of ) while suffering negligible increase in outage. This holds out potential for significant gains in an ad hoc network scenario where minimizing interference to possibly other users as well as conserving power are important considerations.

We consider the diversity-multiplexing tradeoff in half duplex relay channels. In recent work by Azarian et al. [2], it was shown that Dynamic Decode and Forward (DDF) strictly dominates all the other schemes in the high SNR (HSNR) regime, with the inherent assumption that all the links have the same average SNR p. In this work, we introduce geometry into the problem by letting the SNR of different links scale differently with p. We exhaustively identify the tradeoff for DDF and Non- Orthogonal Amplify and Forward (NAF) when the SNRs are different. We show that, even when geometry is included, the dominance behavior of DDF still holds. In some regions, NAF can at most do as well as DDF. We also show that when the multiplexing gain exceeds the exponential order of the SNR of either source to relay or relay to destination channels, the tradeoff curve of DDF reduces to that of direct transmission.