We study the problem of computing deterministic optimal policies for constrained Markov decision processes (MDPs) with continuous state and action spaces, which are widely encountered in constrained dynamical systems. Designing deterministic policy gradient methods in continuous state and action spaces is particularly challenging due to the lack of enumerable state-action pairs and the adoption of deterministic policies, hindering the application of existing policy gradient methods for constrained MDPs. To this end, we develop a deterministic policy gradient primal-dual method to find an optimal deterministic policy with non-asymptotic convergence. Specifically, we leverage regularization of the Lagrangian of the constrained MDP to propose a deterministic policy gradient primal-dual (D-PGPD) algorithm that updates the deterministic policy via a quadratic-regularized gradient ascent step and the dual variable via a quadratic-regularized gradient descent step. We prove that the primal-dual iterates of D-PGPD converge at a sub-linear rate to an optimal regularized primal-dual pair. We instantiate D-PGPD with function approximation and prove that the primal-dual iterates of D-PGPD converge at a sub-linear rate to an optimal regularized primal-dual pair, up to a function approximation error. Furthermore, we demonstrate the effectiveness of our method in two continuous control problems: robot navigation and fluid control. To the best of our knowledge, this appears to be the first work that proposes a deterministic policy search method for continuous-space constrained MDPs.

Graph neural networks (GNNs) have demonstrated their effectiveness in various tasks supported by their generalization capabilities. However, the current analysis of GNN generalization relies on the assumption that training and testing data are independent and identically distributed (i.i.d). This imposes limitations on the cases where a model mismatch exists when generating testing data. In this paper, we examine GNNs that operate on geometric graphs generated from manifold models, explicitly focusing on scenarios where there is a mismatch between manifold models generating training and testing data. Our analysis reveals the robustness of the GNN generalization in the presence of such model mismatch. This indicates that GNNs trained on graphs generated from a manifold can still generalize well to unseen nodes and graphs generated from a mismatched manifold. We attribute this mismatch to both node feature perturbations and edge perturbations within the generated graph. Our findings indicate that the generalization gap decreases as the number of nodes grows in the training graph while increasing with larger manifold dimension as well as larger mismatch. Importantly, we observe a trade-off between the generalization of GNNs and the capability to discriminate high-frequency components when facing a model mismatch. The most important practical consequence of this analysis is to shed light on the filter design of generalizable GNNs robust to model mismatch. We verify our theoretical findings with experiments on multiple real-world datasets.

We introduce Feasible Learning (FL), a sample-centric learning paradigm where models are trained by solving a feasibility problem that bounds the loss for each training sample. In contrast to the ubiquitous Empirical Risk Minimization (ERM) framework, which optimizes for average performance, FL demands satisfactory performance \emph{on every individual data point}. Since any model that meets the prescribed performance threshold is a valid FL solution, the choice of optimization algorithm and its dynamics play a crucial role in shaping the properties of the resulting solutions. In particular, we study a primal-dual approach which dynamically re-weights the importance of each sample during training. To address the challenge of setting a meaningful threshold in practice, we introduce a relaxation of FL that incorporates slack variables of minimal norm. Our empirical analysis, spanning image classification, age regression, and preference optimization in large language models, demonstrates that models trained via FL can learn from data while displaying improved tail behavior compared to ERM, with only a marginal impact on average performance.

In this study, we address the challenge of packet based information routing in large-scale wireless communication networks. We approach this scenario by framing the problem as a statistical learning problem, where each node in the network relies only on the local data. Our exploration focuses on the idea of opportunistic routing, which exploits the broadcast nature of wireless communication to select the optimal relay node and transmit information packets to the destination node via multiple relay nodes. We present a distributed optimization method based on state augmentation (SA) that aims to maximize the total information on different source nodes of the network. Our formulation of the problem deploys graph neural networks (GNNs) to perform graph convolution on the topological connections between the network nodes. Using unsupervised learning, we derive optimal routing policies for the source nodes across multiple flows from the GNN output. Numerical results show the superiority of our proposed method by comparing a GNN model trained against standard algorithms.

The proliferation of digital microscopy images, driven by advances in automated whole slide scanning, presents significant opportunities for biomedical research and clinical diagnostics. However, accurately annotating densely packed information in these images remains a major challenge. To address this, we introduce DiffKillR, a novel framework that reframes cell annotation as the combination of archetype matching and image registration tasks. DiffKillR employs two complementary neural networks: one that learns a diffeomorphism-invariant feature space for robust cell matching and another that computes the precise warping field between cells for annotation mapping. Using a small set of annotated archetypes, DiffKillR efficiently propagates annotations across large microscopy images, reducing the need for extensive manual labeling. More importantly, it is suitable for any type of pixel-level annotation. We will discuss the theoretical properties of DiffKillR and validate it on three microscopy tasks, demonstrating its advantages over existing supervised, semi-supervised, and unsupervised methods.

Positional encodings (PEs) are essential for effective graph representation learning because they provide position awareness in inherently position-agnostic transformer architectures and increase the expressive capacity of Graph Neural Networks (GNNs). However, designing powerful and efficient PEs for graphs poses significant challenges due to the absence of canonical node ordering and the scale of the graph. In this work, we identify four key properties that graph PEs should satisfy: stability, expressive power, scalability, and genericness. We find that existing eigenvector-based PE methods often fall short of jointly satisfying these criteria. To address this gap, we introduce PEARL, a novel framework of learnable PEs for graphs. Our primary insight is that message-passing GNNs function as nonlinear mappings of eigenvectors, enabling the design of GNN architectures for generating powerful and efficient PEs. A crucial challenge lies in initializing node features in a manner that is both expressive and permutation equivariant. We tackle this by initializing GNNs with random node inputs or standard basis vectors, thereby unlocking the expressive power of message-passing operations, while employing statistical pooling functions to maintain permutation equivariance. Our analysis demonstrates that PEARL approximates equivariant functions of eigenvectors with linear complexity, while rigorously establishing its stability and high expressive power. Experimental evaluations show that PEARL outperforms lightweight versions of eigenvector-based PEs and achieves comparable performance to full eigenvector-based PEs, but with one or two orders of magnitude lower complexity. Our code is available at https://github.com/ehejin/Pearl-PE.

The goal of continual learning (CL) is to train a model that can solve multiple tasks presented sequentially. Recent CL approaches have achieved strong performance by leveraging large pre-trained models that generalize well to downstream tasks. However, such methods lack theoretical guarantees, making them prone to unexpected failures. Conversely, principled CL approaches often fail to achieve competitive performance. In this work, we aim to bridge this gap between theory and practice by designing a simple CL method that is theoretically sound and highly performant. Specifically, we lift pre-trained features into a higher dimensional space and formulate an over-parametrized minimum-norm least-squares problem. We find that the lifted features are highly ill-conditioned, potentially leading to large training errors (numerical instability) and increased generalization errors. We address these challenges by continually truncating the singular value decomposition of the lifted features. Our approach, termed LoRanPAC, is stable with respect to the choice of hyperparameters, can handle hundreds of tasks, and outperforms state-of-the-art CL methods on multiple datasets. Importantly, our method satisfies a recurrence relation throughout its continual learning process, which allows us to prove it maintains small training and test errors by appropriately truncating a fraction of SVD factors. This results in a stable continual learning method with strong empirical performance and theoretical guarantees. Code available: \url{https://github.com/liangzu/loranpac}.

Existing approaches based on context prompting or reinforcement learning (RL) to improve the reasoning capacities of large language models (LLMs) depend on the LLMs’ internal knowledge to produce reliable Chain-Of-Thought (CoT). However, no matter the size of LLMs, certain problems cannot be resolved in a single forward pass. Meanwhile, agent-based reasoning systems require access to a comprehensive nonparametric knowledge base, which is often costly or not feasible for use in scientific and niche domains. We present Graph Inspired Veracity Extrapolation (GIVE), a novel reasoning method that merges parametric and non-parametric memories to improve accurate reasoning with minimal external input. GIVE guides the LLM agent to select the most pertinent expert data ($\textbf{observe}$), engage in query-specific associative thinking ($\textbf{reflect}$), and then synthesize this information to produce the final output ($\textbf{speak}$). Extensive experiments demonstrated the following benefits of our framework: (1) GIVE increases the performance of LLMs across various sizes. (2) In some scenarios, GIVE allows smaller LLMs to surpass larger, more sophisticated ones in scientific tasks ($\textbf{GPT3.5T + GIVE > GPT4}$). (3) GIVE is effective on scientific and open-domain assessments. (4) GIVE is a training-free method that enables LLMs to tackle new problems that extend beyond their training data (up to $\textbf{43.5}$% $\rightarrow$ $\textbf{88.2}$% accuracy improvement). (5) GIVE allows LLM agents to reason using both restricted (very small) and noisy (very large) knowledge sources, accommodating knowledge graphs (KG) ranging from $\textbf{135}$ to more than $\textbf{840k}$ nodes. (6) The reasoning process involved in GIVE is fully interpretable. Our code is available at https://github.com/Jason-Tree/GIVE

Graph Neural Networks (GNNs) extend convolutional neural networks to operate on graphs. Despite their impressive performances in various graph learning tasks, the theoretical understanding of their generalization capability is still lacking. Previous GNN generalization bounds ignore the underlying graph structures, often leading to bounds that increase with the number of nodes – a behavior contrary to the one experienced in practice. In this paper, we take a manifold perspective to establish the statistical generalization theory of GNNs on graphs sampled from a manifold in the spectral domain. As demonstrated empirically, we prove that the generalization bounds of GNNs decrease linearly with the size of the graphs in the logarithmic scale, and increase linearly with the spectral continuity constants of the filter functions. Notably, our theory explains both node-level and graph-level tasks. Our result has two implications: i) guaranteeing the generalization of GNNs to unseen data over manifolds; ii) providing insights into the practical design of GNNs, i.e., restrictions on the discriminability of GNNs are necessary to obtain a better generalization performance. We demonstrate our generalization bounds of GNNs using synthetic and multiple real-world datasets.

The multi-objective coverage control problem requires a robot swarm to collaboratively provide sensor coverage to multiple heterogeneous importance density fields (IDFs) simultaneously. We pose this as an optimization problem with constraints and study two different formulations: (1) Fair coverage, where we minimize the maximum coverage cost for any field, promoting equitable resource distribution among all fields; and (2) Constrained coverage, where each field must be covered below a certain cost threshold, ensuring that critical areas receive adequate coverage according to predefined importance levels. We study the decentralized setting where robots have limited communication and local sensing capabilities, making the system more realistic, scalable, and robust. Given the complexity, we propose a novel decentralized constrained learning approach that combines primal-dual optimization with a Learnable Perception-Action-Communication (LPAC) neural network architecture. We show that the Lagrangian of the dual problem can be reformulated as a linear combination of the IDFs, enabling the LPAC policy to serve as a primal solver. We empirically demonstrate that the proposed method (i) significantly outperforms state-of-the-art decentralized controllers by 30% on average in terms of coverage cost, (ii) transfers well to larger environments with more robots, and (iii) is scalable in the number of IDFs and robots in the swarm.

Diffusion models have become prevalent in generative modeling due to their ability to sample from complex distributions. To improve the quality of generated samples and their compliance with user requirements, two commonly used methods are: (i) Alignment, which involves finetuning a diffusion model to align it with a reward; and (ii) Composition, which combines several pretrained diffusion models together, each emphasizing a desirable attribute in the generated outputs. However, trade-offs often arise when optimizing for multiple rewards or combining multiple models, as they can often represent competing properties. Existing methods cannot guarantee that the resulting model faithfully generates samples with all the desired properties. To address this gap, we propose a constrained optimization framework that unifies alignment and composition of diffusion models by enforcing that the aligned model satisfies reward constraints and/or remains close to each pretrained model. We provide a theoretical characterization of the solutions to the constrained alignment and composition problems and develop a Lagrangian-based primal-dual training algorithm to approximate these solutions. Empirically, we demonstrate our proposed approach in image generation, applying it to alignment and composition, and show that our aligned or composed model satisfies constraints effectively. Our implementation can be found at: https://github.com/shervinkhalafi/constrained_comp_align.

We study the problem of computing an optimal large language model (LLM) policy for the constrained alignment problem, where the goal is to maximize a primary reward objective while satisfying constraints on secondary utilities. Despite the popularity of Lagrangian-based LLM policy search in constrained alignment, iterative primal-dual methods often fail to converge, and non-iterative dual-based methods do not achieve optimality in the LLM parameter space. To address these challenges, we employ Lagrangian duality to develop an iterative dual-based alignment method that alternates between updating the LLM policy via Lagrangian maximization and updating the dual variable via dual descent. In theory, we characterize the primal-dual gap between the primal value in the distribution space and the dual value in the LLM parameter space. We further quantify the optimality gap of the learned LLM policies at near-optimal dual variables with respect to both the objective and the constraint functions. These results prove that dual-based alignment methods can find an optimal constrained LLM policy, up to an LLM parametrization gap. We demonstrate the effectiveness and merits of our approach through extensive experiments conducted on the PKU-SafeRLHF and Anthropic HH-RLHF datasets.

Coverage control is the problem of navigating a robot swarm to collaboratively monitor features or a phenomenon of interest not knowna priori. The problem is challenging in decentralized settings with robots that have limited communication and sensing capabilities. We propose a learnable Perception-Action-Communication (LPAC) architecture for the problem, wherein a convolutional neural network (CNN) processes localized perception; a graph neural network (GNN) facilitates robot communications; finally, a shallow multi-layer perceptron (MLP) computes robot actions. The GNN enables collaboration in the robot swarm by computingwhatinformation to communicate with nearby robots andhowto incorporate received information. Evaluations show that the LPAC models—trained using imitation learning—outperform standard decentralized and centralized coverage control algorithms. The learned policy generalizes to environments different from the training dataset, transfers to larger environments with more robots, and is robust to noisy position estimates. The results indicate the suitability of LPAC architectures for decentralized navigation in robot swarms to achieve collaborative behavior.

We study a class of constrained reinforcement learning (RL) problems in which multiple constraint specifications are not identified before training. It is challenging to identify appropriate constraint specifications due to the undefined trade-off between the reward maximization objective and the constraint satisfaction, which is ubiquitous in constrained decision-making. To tackle this issue, we propose a new constrained RL approach that searches for policy and constraint specifications together. This method features the adaptation of relaxing the constraint according to a relaxation cost introduced in the learning objective. Since this feature mimics how ecological systems adapt to disruptions by altering operation, our approach is termed as resilient constrained RL. Specifically, we provide a set of sufficient conditions that balance the constraint satisfaction and the reward maximization in notion of resilient equilibrium, propose a tractable formulation of resilient constrained policy optimization that takes this equilibrium as an optimal solution, and advocate two resilient constrained policy search algorithms with non-asymptotic convergence guarantees on the optimality gap and constraint satisfaction. Furthermore, we demonstrate the merits and the effectiveness of our approach in computational experiments.

Network slicing is a key feature in 5G/NG cellular networks that creates customized slices for different service types with various quality-of-service (QoS) requirements, which can achieve service differentiation and guarantee service-level agreement (SLA) for each service type. In Wi-Fi networks, there is limited prior work on slicing, and a potential solution is based on a multi-tenant architecture on a single access point (AP) that dedicates different channels to different slices. In this paper, we define a flexible, constrained learning framework to enable slicing in Wi-Fi networks subject to QoS requirements. We specifically propose an unsupervised learning-based network slicing method that leverages a state-augmented primal-dual algorithm, where a neural network policy is trained offline to optimize a Lagrangian function and the dual variable dynamics are updated online in the execution phase. We show that state augmentation is crucial for generating slicing decisions that meet the ergodic QoS requirements.

We consider the problem of routing network packets in a large-scale communication system where the nodes have access to only local information. We formulate this problem as a constrained learning problem, which can be solved using a distributed optimization algorithm. We approach this distributed optimization using a novel state-augmentation (SA) strategy to maximize the aggregate information packets at different source nodes, leveraging dual variables corresponding to flow constraint violations. The construction is based on graph neural networks (GNNs) that employ graph convolutions over the underlying communication network topology. We devise an unsupervised learning algorithm to transform the output of the GNN architecture into optimal routing decisions. The proposed method takes advantage of only the local information available at each node and efficiently routes the desired packets to the destination. We provide numerical results demonstrating the superiority of the proposed method over baseline routing algorithms.

Graph Neural Networks (GNNs) are powerful architectures that have demonstrated remarkable performance in various node-level and graph-level tasks. Despite this success, prominent analysis shows that their representation power is limited and that they are at most as expressive as the Weisfeiler-Lehman (WL) test. In this paper, we take a different approach and analyze the expressive power of GNNs with respect to the spectral decomposition of the graph operators. We prove that GNNs can produce distinct equivariant outputs for all graphs with different eigenvalues, therefore surpassing the limitations of the WL test. On the practical front, our approach enables the design of GNNs that unlock the full potential of their expressive power. Thorough experimental analysis on graph classification datasets supports our theoretical findings and showcases the effectiveness of the proposed approach.

Optimal power flow is a critical optimization problem that allocates power to the generators in order to satisfy the demand at a minimum cost. This is a non-convex problem shown to be NP-hard. We use a graph neural network to learn a nonlinear function between the power demanded and the corresponding allocation. We learn the solution in an unsupervised manner, minimizing the cost directly. To consider the power system constraints, we propose a novel barrier method that is differentiable and works on initially infeasible points. We show through simulations that the use of graph neural networks in this unsupervised learning context leads to solutions comparable to standard solvers while being computationally efficient and avoiding constraint violations.

In this paper we discuss the results recently published in [1] about algebraic signal models (ASMs) based on non commutative algebras and their use in convolutional neural networks. Relying on the general tools from algebraic signal processing (ASP), we study the filtering and stability properties of non commutative convolutional filters. We show how non commutative filters can be stable to small perturbations on the space of operators. We also show that although the spectral components of the Fourier representation in a non commutative signal model are associated to spaces of dimension larger than one, there is a trade-off between stability and selectivity similar to that observed for commutative models. Our results have direct implications for group neural networks, multigraph neural networks and quaternion neural networks, among other non commutative architectures. We conclude by corroborating these results through numerical experiments.

With the widespread adoption of machine learning systems, the need to curtail their behavior has become increasingly apparent. This is evidenced by recent advancements towards developing models that satisfy robustness, safety, and fairness requirements. These requirements can be imposed (with generalization guarantees) by formulating constrained learning problems that can then be tackled by dual ascent algorithms. Yet, though these algorithms converge in objective value, even in non-convex settings, they cannot guarantee that their outcome is feasible. Doing so requires randomizing over all iterates, which is impractical in virtually any modern applications. Still, final iterates have been observed to perform well in practice. In this work, we address this gap between theory and practice by characterizing the constraint violation of Lagrangian minimizers associated with optimal dual variables, despite lack of convexity. To do this, we leverage the fact that non-convex, finite-dimensional constrained learning problems can be seen as parametrizations of convex, functional problems. Our results show that rich parametrizations effectively mitigate the issue of feasibility in dual methods, shedding light on prior empirical successes of dual learning. We illustrate our findings in fair learning tasks.

Graph Neural Networks (GNNs) are powerful representation learning tools that have achieved remarkable performance in various downstream tasks. However, there are still open questions regarding their ability to count and list substructures, which play a crucial role in biological and social networks. In this work, we fill this gap and characterize the representation {and generalization} power of GNNs in terms of their ability to produce powerful representations that count substructures. In particular, we study the message-passing operations of GNNs with random node input in a novel fashion, and show how they can produce equivariant representations that are associated with high-order statistical moments. Using these representations, we prove that GNNs can learn how to count cycles, {cliques}, quasi-cliques, and the number of connected components in a graph. We also provide new insights into the generalization capacity of GNNs. Our analysis is constructive and enables the design of a generic GNN architecture that shows remarkable performance in four distinct tasks: cycle detection, cycle counting, graph classification, and molecular property prediction.

Several applications in time series forecasting require predicting multiple steps ahead. Despite the vast amount of literature in the topic, both classical and recent deep learning based approaches have mostly focused on minimising performance averaged over the predicted window. We observe that this can lead to disparate distributions of errors across forecasting steps, especially for recent transformer architectures trained on popular forecasting benchmarks. That is, optimising performance on average can lead to undesirably large errors at specific time-steps. In this work, we present a Constrained Learning approach for long-term time series forecasting that aims to find the best model in terms of average performance that respects a user-defined upper bound on the loss at each time-step. We call our approach loss shaping constraints because it imposes constraints on the loss at each time step, and leverage recent duality results to show that despite its non-convexity, the resulting problem has a bounded duality gap. We propose a practical primal-dual algorithm to tackle it, and demonstrate that the proposed approach exhibits competitive average performance in time series forecasting benchmarks, while shaping the distribution of errors across the predicted window.

Neural tangent kernels (NTKs) provide a theoretical regime to analyze the learning and generalization behavior of over-parametrized neural networks. For a supervised learning task, the association between the eigenvectors of the NTK and given data (a concept referred to as alignment in this paper) can govern the rate of convergence of gradient descent, as well as generalization to unseen data. Building upon this concept and leveraging the structure of NTKs for graph neural networks (GNNs), we theoretically investigate NTKs and alignment, where our analysis reveals that optimizing the alignment translates to optimizing the graph representation or the graph shift operator (GSO) in a GNN. Our results further establish theoretical guarantees on the optimality of the alignment for a two-layer GNN and these guarantees are characterized by the graph shift operator being a function of the cross-covariance between the input and the output data. The theoretical insights drawn from the analysis of NTKs are validated by our experiments focused on a multi-variate time series prediction task for a publicly available dataset. Specifically, they demonstrate that GNN-based learning models that operate on the cross-covariance matrix indeed outperform those that operate on the covariance matrix estimated from only the input data.

In this paper we present a new approach to Mobile Infrastructure on Demand (MID) where a dedicated team of robots creates and sustains a wireless network that satisfies the communication requirements of a different team of task-oriented robots seeking to coordinate their actions in the absence of existing communication infrastructure. Different from previous works, our approach forgoes heuristics for network performance such as algebraic-connectivity or network flow optimizations and instead positions communication support robots to directly maximize the probability of packet delivery by the underlying opportunistic routing protocol. Our system is task agnostic and practical to implement and operate on robots equipped with off-the-shelf WiFi radios. We demonstrate this through a set of experiments showing our MID system maintaining the delivery of critical mission data in a situational awareness setting and enabling foraging robots to effectively coordinate their actions during multi-robot exploration.

Diffusion models have attained prominence for their ability to synthesize a probability distribution for a given dataset via a diffusion process, enabling the generation of new data points with high fidelity. However, diffusion processes are prone to generating samples that reflect biases in a training dataset. To address this issue, we develop constrained diffusion models by imposing diffusion constraints based on desired distributions that are informed by requirements. Specifically, we cast the training of diffusion models under requirements as a constrained distribution optimization problem that aims to reduce the distribution difference between original and generated data while obeying constraints on the distribution of generated data. We show that our constrained diffusion models generate new data from a mixture data distribution that achieves the optimal trade-off among objective and constraints. To train constrained diffusion models, we develop a dual training algorithm and characterize the optimality of the trained constrained diffusion model. We empirically demonstrate the effectiveness of our constrained models in two constrained generation tasks: (i) we consider a dataset with one or more underrepresented classes where we train the model with constraints to ensure fairly sampling from all classes during inference; (ii) we fine-tune a pre-trained diffusion model to sample from a new dataset while avoiding overfitting.

Despite the prevalence of wireless connectivity in urban areas around the globe, there remain numerous and diverse situations where connectivity is insufficient or unavailable. To address this, we introducemobile wireless infrastructure on demand, a system of unmanned aerial vehicles (UAVs) that can be rapidly deployed to establish an ad hoc wireless network. This network has the capability of reconfiguring itself dynamically to satisfy and maintain the required quality of communication. The system optimizes the positions of the UAVs and the routing of data flows throughout the network to achieve this Quality of Service (QoS). By these means, task agents using the network simply request a desired QoS, and the system adapts accordingly while allowing them to move freely. We have validated this system both in simulation and in real-world experiments. The results demonstrate that our system effectively offers mobile wireless infrastructure on demand, extending the operational range of task agents and supporting complex mobility patterns, all while ensuring connectivity and being resilient to agent failures.

In this work we introduce a convolution operation over the tangent bundle of Riemannian manifolds exploiting the Connection Laplacian operator. We use this convolution operation to define tangent bundle filters and tangent bundle neural networks (TNNs), novel continuous architectures operating on tangent bundle signals, i.e. vector fields over manifolds. We discretize TNNs both in space and time domains, showing that their discrete counterpart is a principled variant of the recently introduced Sheaf Neural Networks. We formally prove that this discrete architecture converges to the underlying continuous TNN. We numerically evaluate the effectiveness of the proposed architecture on a denoising task of a tangent vector field over the unit 2-sphere.

In this paper, we introduce a convolutional architecture to perform learning when information is supported on multigraphs. Exploiting algebraic signal processing (ASP), we propose a convolutional signal processing model on multigraphs (MSP). Then, we introduce multigraph convolutional neural networks (MGNNs) as stacked and layered structures where information is processed according to an MSP model. We also develop a procedure for tractable computation of filter coefficients in the MGNN and a low cost method to reduce the dimensionality of the information transferred between layers. We conclude by comparing the performance of MGNNs against other learning architectures on an optimal resource allocation task for multi-channel communication systems.

Multi-task learning aims to acquire a set of functions, either regressors or classifiers, that perform well for diverse tasks. At its core, the idea behind multi-task learning is to exploit the intrinsic similarity across data sources to aid in the learning process for each individual domain. In this paper we draw intuition from the two extreme learning scenarios – a single function for all tasks, and a task-specific function that ignores the other tasks dependencies – to propose a bias-variance trade-off. To control the relationship between the variance (given by the number of i.i.d. samples), and the bias (coming from data from other task), we introduce a constrained learning formulation that enforces domain specific solutions to be close to a central function. This problem is solved in the dual domain, for which we propose a stochastic primal-dual algorithm. Experimental results for a multi-domain classification problem with real data show that the proposed procedure outperforms both the task specific, as well as the single classifiers.

Graph Neural Networks (GNNs) rely on graph convolutions to exploit meaningful patterns in networked data. Based on matrix multiplications, convolutions incur in high computational costs leading to scalability limitations in practice. To overcome these limitations, proposed methods rely on training GNNs in smaller number of nodes, and then transferring the GNN to larger graphs. Even though these methods are able to bound the difference between the output of the GNN with different number of nodes, they do not provide guarantees against the optimal GNN on the very large graph. In this paper, we propose to learn GNNs on very large graphs by leveraging the limit object of a sequence of growing graphs, the graphon. We propose to grow the size of the graph as we train, and we show that our proposed methodology – learning by transference – converges to a neighborhood of a first order stationary point on the graphon data. A numerical experiment validates our proposed approach.

Space-time graph neural networks (ST-GNNs) are recently developed architectures that learn efficient graph representations of time-varying data. ST-GNNs are particularly useful in multi-agent systems, due to their stability properties and their ability to respect communication delays between the agents. In this paper we revisit the stability properties of ST-GNNs and prove that they are stable to stochastic graph perturbations. Our analysis suggests that ST-GNNs are suitable for transfer learning on time-varying graphs and enables the design of generalized convolutional architectures that jointly process time-varying graphs and time-varying signals. Numerical experiments on decentralized control systems validate our theoretical results and showcase the benefits of traditional and generalized ST-GNN architectures.

Enabling low precision implementations of deep learning models, without considerable performance degradation, is necessary in resource and latency constrained settings. Moreover, exploiting the differences in sensitivity to quantization across layers can allow mixed precision implementations to achieve a considerably better computation performance trade-off. However, backpropagating through the quantization operation requires introducing gradient approximations, and choosing which layers to quantize is challenging for modern architectures due to the large search space. In this work, we present a constrained learning approach to quantization aware training. We formulate low precision supervised learning as a constrained optimization problem, and show that despite its non-convexity, the resulting problem is strongly dual and does away with gradient estimations. Furthermore, we show that dual variables indicate the sensitivity of the objective with respect to constraint perturbations. We demonstrate that the proposed approach exhibits competitive performance in image classification tasks, and leverage the sensitivity result to apply layer selective quantization based on the value of dual variables, leading to considerable performance improvements.

Group convolutional neural networks are a useful tool for utilizing symmetries known to be in a signal; however, they require that the signal is defined on the group itself. Existing approaches either work directly with group signals, or they impose a lifting step with heuristics to compute the convolution which can be computationally costly. Taking an algebraic signal processing perspective, we propose a novel convolutional filter from the Lie group algebra directly, thereby removing the need to lift altogether. Furthermore, we establish stability of the filter by drawing connections to multigraph signal processing. The proposed filter is evaluated on a classification problem on two datasets with SO(3) group symmetries.

The deviation between chronological age and biological age is a well-recognized biomarker associated with cognitive decline and neurodegeneration. Age-related and pathology-driven changes to brain structure are captured by various neuroimaging modalities. These datasets are characterized by high dimensionality as well as collinearity, hence applications of graph neural networks in neuroimaging research routinely use sample covariance matrices as graphs. We have recently studied covariance neural networks (VNNs) that operate on sample covariance matrices using the architecture derived from graph convolutional networks, and we showed VNNs enjoy significant advantages over traditional data analysis approaches. In this paper, we demonstrate the utility of VNNs in inferring brain age using cortical thickness data. Furthermore, our results show that VNNs exhibit multi-scale and multi-site transferability for inferring brain age. In the context of brain age in Alzheimer’s disease (AD), our experiments show that i) VNN outputs are interpretable as brain age predicted using VNNs is significantly elevated as compared to the chronological age for AD with respect to healthy subjects for different datasets; and ii) VNNs can be transferable, i.e., VNNs trained on one dataset can be transferred to another dataset with different dimensionality without retraining for brain age prediction.

The increasing availability of geometric data has motivated the need for information processing over non-Euclidean domains modeled as manifolds. The building block for information processing architectures with desirable theoretical properties such as invariance and stability is convolutional filtering. Manifold convolutional filters are defined from the manifold diffusion sequence, constructed by successive applications of the Laplace-Beltrami operator to manifold signals. However, the continuous manifold model can only be accessed by sampling discrete points and building an approximate graph model from the sampled manifold. Effective linear information processing on the manifold requires quantifying the error incurred when approximating manifold convolutions with graph convolutions. In this paper, we derive a non-asymptotic error bound for this approximation, showing that convolutional filtering on the sampled manifold converges to continuous manifold filtering. Our findings are further demonstrated empirically on a problem of navigation control.

Smoothness and low dimensional structures play central roles in improving generalization and stability in learning and statistics. This work combines techniques from semi-infinite constrained learning and manifold regularization to learn representations that are globally smooth on a manifold. To do so, it shows that under typical conditions the problem of learning a Lipschitz continuous function on a manifold is equivalent to a dynamically weighted manifold regularization problem. This observation leads to a practical algorithm based on a weighted Laplacian penalty whose weights are adapted using stochastic gradient techniques. It is shown that under mild conditions, this method estimates the Lipschitz constant of the solution, learning a globally smooth solution as a byproduct. Experiments on real world data illustrate the advantages of the proposed method relative to existing alternatives. Our code is available at https://github.com/JuanCervino/smoothbench.

Underlying data structures, such as symmetries or invariance to transformations, are often exploited to improve the solution of learning tasks. However, embedding these properties in models or learning algorithms can be challenging and computationally intensive. Data augmentation, on the other hand, induces these symmetries during training by applying multiple transformations to the input data. Despite its ubiquity, its effectiveness depends on the choices of which transformations to apply, when to do so, and how often. In fact, there is both empirical and theoretical evidence that the indiscriminate use of data augmentation can introduce biases that outweigh its benefits. This work tackles these issues by automatically adapting the data augmentation while solving the learning task. To do so, it formulates data augmentation as an invariance constrained learning problem and leverages Monte Carlo Markov Chain (MCMC) sampling to solve it. The result is an algorithm that not only does away with a priori searches for augmentation distributions, but also dynamically controls if and when data augmentation is applied. We validate empirically our theoretical developments in automatic data augmentation benchmarks for CIFAR and ImageNet-100 datasets. Furthermore, our experiments show how this approach can be used to gather insights on the actual symmetries underlying a learning task.

This paper addresses the problem of active collaborative localization in heterogeneous robot teams with unknown data association. It involves positioning a small number of identical unmanned ground vehicles (UGVs) at desired positions so that an unmanned aerial vehicle (UAV) can, through unlabelled measurements of UGVs, uniquely determine its global pose. We model the problem as a sequential two player game, in which the first player positions the UGVs and the second identifies the two distinct hypothetical poses of the UAV at which the sets of measurements to the UGVs differ by as little as possible. We solve the underlying problem from the vantage point of the first player for a subclass of measurement models using a mixture of local optimization and exhaustive search procedures. Real-world experiments with a team of UAV and UGVs show that our method can achieve centimeter-level global localization accuracy. We also show that our method consistently outperforms random positioning of UGVs by a large margin, with as much as a 90% reduction in position and angular estimation error. Our method can tolerate a significant amount of random as well as non-stochastic measurement noise. This indicates its potential for reliable state estimation on board size, weight, and power (SWaP) constrained UAVs. This work enables robust localization in perceptually-challenged GPS-denied environments, thus paving the road for large-scale multi-robot navigation and mapping.

We study the problem of computing an optimal policy of an infinite-horizon discounted constrained Markov decision process (constrained MDP). Despite the popularity of Lagrangian-based policy search methods used in practice, the oscillation of policy iterates in these methods has not been fully understood, bringing out issues such as violation of constraints and sensitivity to hyper-parameters. To fill this gap, we employ the Lagrangian method to cast a constrained MDP into a constrained saddle-point problem in which max/min players correspond to primal/dual variables, respectively, and develop two single-time-scale policy-based primal-dual algorithms with non-asymptotic convergence of their policy iterates to an optimal constrained policy. Specifically, we first propose a regularized policy gradient primal-dual (RPG-PD) method that updates the policy using an entropy-regularized policy gradient, and the dual variable via a quadratic-regularized gradient ascent, simultaneously. We prove that the policy primal-dual iterates of RPG-PD converge to a regularized saddle point with a sublinear rate, while the policy iterates converge sublinearly to an optimal constrained policy. We further instantiate RPG-PD in large state or action spaces by including function approximation in policy parametrization, and establish similar sublinear last-iterate policy convergence. Second, we propose an optimistic policy gradient primal-dual (OPG-PD) method that employs the optimistic gradient method to update primal/dual variables, simultaneously. We prove that the policy primal-dual iterates of OPG-PD converge to a saddle point that contains an optimal constrained policy, with a linear rate. To the best of our knowledge, this work appears to be the first non-asymptotic policy last-iterate convergence result for single-time-scale algorithms in constrained MDPs. We further validate the merits and the effectiveness of our methods in computational experiments.

When deploying machine learning solutions, they must satisfy multiple requirements beyond accuracy, such as fairness, robustness, or safety. These requirements are imposed during training either implicitly, using penalties, or explicitly, using constrained optimization methods based on Lagrangian duality. Either way, specifying requirements is hindered by the presence of compromises and limited prior knowledge about the data. Furthermore, their impact on performance can often only be evaluated by actually solving the learning problem. This paper presents a constrained learning approach that adapts the requirements while simultaneously solving the learning task. To do so, it relaxes the learning constraints in a way that contemplates how much they affect the task at hand by balancing the performance gains obtained from the relaxation against a user-defined cost of that relaxation. We call this approach resilient constrained learning after the term used to describe ecological systems that adapt to disruptions by modifying their operation. We show conditions under which this balance can be achieved and introduce a practical algorithm to compute it, for which we derive approximation and generalization guarantees. We showcase the advantages of this resilient learning method in image classification tasks involving multiple potential invariances and in federated learning under distribution shift.

In computational neuroscience, there has been an increased interest in developing machine learning algorithms that leverage brain imaging data to provide estimates of "brain age" for an individual. Importantly, the discordance between brain age and chronological age (referred to as "brain age gap") can capture accelerated aging due to adverse health conditions and therefore, can reflect increased vulnerability towards neurological disease or cognitive impairments. However, widespread adoption of brain age for clinical decision support has been hindered due to lack of transparency and methodological justifications in most existing brain age prediction algorithms. In this paper, we leverage coVariance neural networks (VNN) to propose an explanation-driven and anatomically interpretable framework for brain age prediction using cortical thickness features. Specifically, our brain age prediction framework extends beyond the coarse metric of brain age gap in Alzheimer’s disease (AD) and we make two important observations: (i) VNNs can assign anatomical interpretability to elevated brain age gap in AD by identifying contributing brain regions, (ii) the interpretability offered by VNNs is contingent on their ability to exploit specific eigenvectors of the anatomical covariance matrix. Together, these observations facilitate an explainable and anatomically interpretable perspective to the task of brain age prediction.

Though learning has become a core component of modern information processing, there is now ample evidence that it can lead to biased, unsafe, and prejudiced systems. The need to impose requirements on learning is therefore paramount, especially as it reaches critical applications in social, industrial, and medical domains. However, the non-convexity of most modern statistical problems is only exacerbated by the introduction of constraints. Whereas good unconstrained solutions can often be learned using empirical risk minimization, even obtaining a model that satisfies statistical constraints can be challenging. All the more so, a good one. In this paper, we overcome this issue by learning in the empirical dual domain, where constrained statistical learning problems become unconstrained and deterministic. We analyze the generalization properties of this approach by bounding the empirical duality gap -- i.e., the difference between our approximate, tractable solution and the solution of the original (non-convex) statistical problem -- and provide a practical constrained learning algorithm. These results establish a constrained counterpart to classical learning theory, enabling the explicit use of constraints in learning. We illustrate this theory and algorithm in rate-constrained learning applications arising in fairness and adversarial robustness.

The Fokker-Planck equation (FPE) is the partial differential equation that governs the density evolution of the Ito process and is of great importance to the literature of statistical physics and machine learning. The FPE can be regarded as a continuity equation where the change of the density is completely determined by a time varying velocity field. Importantly, this velocity field also depends on the current density function. As a result, the ground-truth velocity field can be shown to be the solution of a fixed-point equation, a property that we call self-consistency. In this paper, we exploit this concept to design a potential function of the hypothesis velocity fields, and prove that, if such a function diminishes to zero during the training procedure, the trajectory of the densities generated by the hypothesis velocity fields converges to the solution of the FPE in the Wasserstein-2 sense. The proposed potential function is amenable to neural-network based parameterization as the stochastic gradient with respect to the parameter can be efficiently computed. Once a parameterized model, such as Neural Ordinary Differential Equation is trained, we can generate the entire trajectory to the FPE.

Graph Neural Networks (GNN) rely on graph convolutions to learn features from network data. GNNs are stable to different types of perturbations of the underlying graph, a property that they inherit from graph filters. In this paper we leverage the stability property of GNNs as a typing point in order to seek for representations that are stable within a distribution. We propose a novel constrained learning approach by imposing a constraint on the stability condition of the GNN within a perturbation of choice. We showcase our framework in real world data, corroborating that we are able to obtain more stable representations while not compromising the overall accuracy of the predictor.

We consider the problem of power control in wireless networks, consisting of multiple transmitter-receiver pairs communicating with each other over a single shared wireless medium. To achieve both a high total rate and a level of fairness across users, we formulate a policy optimization problem with constraints on the minimum per-user rate across network configurations with an adaptive slack parameter. To apply unsupervised learning algorithms in the dual domain, we parameterize the power control policy, slack variable, and dual parameters using graph neural networks (GNNs), which leverage the network topology to create a scalable and network-invariant processing architecture. We use a primal- dual algorithm to learn the optimal GNN parameters and demonstrate via numerical simulations the resulting GNNs' success in achieving the right balance between sum- and 5thpercentile rates throughout a range of network configurations.

We consider the problem of resource allocation in large scale wireless networks. When contextualizing wireless network structures as graphs, we can model the limits of very large wireless systems as manifolds. To solve the problem in the machine learning framework, we propose the use of Manifold Neural Networks (MNNs) as a policy parametrization. In this work, we prove the stability of MNN resource allocation policies under the absolute perturbations to the Laplace-Beltrami operator of the manifold, representing system noise and dynamics present in wireless systems. These results establish the use of MNNs in achieving stable and transferable allocation policies for large scale wireless networks. We verify our results in numerical simulations that show superior performance.

Graph Neural Networks (GNNs) show impressive performance in many practical scenarios, which can be largely attributed to their stability properties. Empirically, GNNs can scale well on large size graphs, but this is contradicted by the fact that existing stability bounds grow with the number of nodes. Graphs with well-defined limits can be seen as samples from manifolds. Hence, in this paper, we analyze the stability properties of convolutional neural networks on manifolds to understand the stability of GNNs on large graphs. Specifically, we focus on stability to relative perturbations of the Laplace-Beltrami operator. To start, we construct frequency ratio threshold filters which separate the infinite-dimensional spectrum of the Laplace-Beltrami operator. We then prove that manifold neural networks composed of these filters are stable to relative operator perturbations. As a product of this analysis, we observe that manifold neural networks exhibit a trade-off between stability and discriminability. Finally, we illustrate our results empirically in a wireless resource allocation scenario where the transmitter-receiver pairs are assumed to be sampled from a manifold.

This paper develops a decentralized approach to mobile sensor coverage by a multi-robot system. We consider a scenario where a team of robots with limited sensing range must position itself to effectively detect events of interest in a region characterized by areas of varying importance. Towards this end, we develop a decentralized control policy for the robots-realized via a Graph Neural Network-which uses inter-robot communication to leverage non-local information for control decisions. By explicitly sharing information between multi-hop neighbors, the decentralized controller achieves a higher quality of coverage when compared to classical approaches that do not communicate and leverage only local information available to each robot. Simulated experiments demonstrate the efficacy of multi-hop communication for multi-robot coverage and evaluate the scalability and transferability of the learning-based controllers.

We consider the pool-based active learning problem, where only a subset of the training data is labeled, and the goal is to query a batch of unlabeled samples to be labeled so as to maximally improve model performance. We formulate the problem using constrained learning, where a set of constraints bounds the performance of the model on labeled samples. Considering a primal-dual approach, we optimize the primal variables, corresponding to the model parameters, as well as the dual variables, corresponding to the constraints. As each dual variable indicates how significantly the perturbation of the respective constraint affects the optimal value of the objective function, we use it as a proxy of the informativeness of the corresponding training sample. Our approach, which we refer to as Active Learning via Lagrangian dualitY, or ALLY, leverages this fact to select a diverse set of unlabeled samples with the highest estimated dual variables as our query set. We demonstrate the benefits of our approach in a variety of classification and regression tasks and discuss its limitations depending on the capacity of the model used and the degree of redundancy in the dataset. We also examine the impact of the distribution shift induced by active sampling and show that ALLY can be used in a generative mode to create novel, maximally-informative samples.

Graph neural networks (GNN) are an effective framework that exploit inter-relationships within graph-structured data for learning. Principal component analysis (PCA) involves the projection of data on the eigenspace of the covariance matrix and draws similarities with the graph convolutional filters in GNNs. Motivated by this observation, we study a GNN architecture, called coVariance neural network (VNN), that operates on sample covariance matrices as graphs. We theoretically establish the stability of VNNs to perturbations in the covariance matrix, thus, implying an advantage over standard PCA-based data analysis approaches that are prone to instability due to principal components associated with close eigenvalues. Our experiments on real-world datasets validate our theoretical results and show that VNN performance is indeed more stable than PCA-based statistical approaches. Moreover, our experiments on multi-resolution datasets also demonstrate that VNNs are amenable to transferability of performance over covariance matrices of different dimensions; a feature that is infeasible for PCA-based approaches.

Driven by the outstanding performance of neural networks in the structured euclidean domain, recent years have seen a surge of interest in developing neural networks for graphs and data supported on graphs. The graph is leveraged at each layer of the neural network as a parameterization to capture detail at the node level with a reduced number of parameters and computational complexity. Following this rationale, this paper puts forth a general framework that unifies state-of-the-art graph neural networks (GNNs) through the concept of EdgeNet. An EdgeNet is a GNN architecture that allows different nodes to use different parameters to weigh the information of different neighbors. By extrapolating this strategy to more iterations between neighboring nodes, the EdgeNet learns edge- and neighbor-dependent weights to capture local detail. This is a general linear and local operation that a node can perform and encompasses under one formulation all existing graph convolutional neural networks (GCNNs) as well as graph attention networks (GATs). In writing different GNN architectures with a common language, EdgeNets highlight specific architecture advantages and limitations, while providing guidelines to improve their capacity without compromising their local implementation. For instance, we show that GCNNs have a parameter sharing structure that induces permutation equivariance. This can be an advantage or a limitation, depending on the application. In cases where it is a limitation, we propose hybrid approaches and provide insights to develop several other solutions that promote parameter sharing without enforcing permutation equivariance. Another interesting conclusion is the unification of GCNNs and GATs —approaches that have been so far perceived as separate. In particular, we show that GATs are GCNNs on a graph that is learned from the features. This particularization opens the doors to develop alternative attention mechanisms for improving discriminatory power.

This paper investigates the general problem of resource allocation for mitigating channel fading effects in Free Space Optical (FSO) communications. The resource allocation problem is modeled as the constrained stochastic optimization framework, which covers a variety of FSO scenarios involving power adaptation, relay selection and their joint allocation. Under this framework, we propose two algorithms that solve FSO resource allocation problems. We first present the Stochastic Dual Gradient (SDG) algorithm that is shown to solve the problem exactly by exploiting the strong duality but whose implementation necessarily requires explicit and accurate system models. As an alternative we present the Primal-Dual Deep Learning (PDDL) algorithm based on the SDG algorithm, which parameterizes the resource allocation policy with Deep Neural Networks (DNNs) and optimizes the latter via a primal-dual method. The parameterized resource allocation problem incurs only a small loss of optimality due to the strong representational power of DNNs, and can be moreover implemented without knowledge of system models. A wide set of numerical experiments are performed to corroborate the proposed algorithms in FSO resource allocation problems. We demonstrate their superior performance and computational efficiency compared to the baseline methods in both continuous power allocation and binary relay selection settings.

Dynamical systems comprised of autonomous agents arise in many relevant problems such as multi-agent robotics, smart grids, or smart cities. Controlling these systems is of paramount importance to guarantee a successful deployment. Optimal centralized controllers are readily available but face limitations in terms of scalability and practical implementation. Optimal decentralized controllers, on the other hand, are difficult to find. In this paper, we propose a framework using graph neural networks (GNNs) to learn decentralized controllers from data. While GNNs are naturally distributed architectures, making them perfectly suited for the task, we adapt them to handle delayed communications as well. Furthermore, they are equivariant and stable, leading to good scalability and transferability properties. The problem of flocking is explored to illustrate the potential of GNNs in learning decentralized controllers.

Stochastic graph neural networks (SGNNs) are information processing architectures that can learn representations from data over random graphs. SGNNs are trained with respect to the expected performance, but this training comes with no guarantee about the deviation of particular output realizations around the optimal mean. To overcome this issue, we propose a learning strategy for SGNNs based on a variance constrained optimization problem, balancing the expected performance and the stochastic deviation. To handle the variance constraint in the stochastic optimization problem, training is undertaken in the dual domain. We propose an alternating primal-dual learning algorithm that updates the primal variable (SGNN parameters) with gradient descent and the dual variable with gradient ascent. We show the stochastic deviation is explicitly controlled through Chebyshev inequality and analyze the optimality loss induced by the primal-dual learning. Through numerical simulations, we observe a strong performance in expectation with a controllable deviation corroborating the theoretical findings.

Graph neural networks (GNNs) learn representations from network data with naturally distributed architectures, rendering them well-suited candidates for decentralized learning. Oftentimes, this decentralized graph support changes with time due to link failures or topology variations. These changes create a mismatch between the graphs on which GNNs were trained and the ones on which they are tested. Online learning can be used to retrain GNNs at testing time, overcoming this issue. However, most online algorithms are centralized and work on convex problems (which GNNs rarely lead to). This paper proposes the Wide and Deep GNN (WD-GNN), a novel architecture that can be easily updated with distributed online learning mechanisms. The WD-GNN comprises two components: the wide part is a bank of linear graph filters and the deep part is a GNN. At training time, the joint architecture learns a nonlinear representation from data. At testing time, the deep part (nonlinear) is left unchanged, while the wide part is retrained online, leading to a convex problem. We derive convergence guarantees for this online retraining procedure and further propose a decentralized alternative. Experiments on the robot swarm control for flocking corroborate theory and show potential of the proposed architecture for distributed online learning.

Decentralized coordination of a robot swarm requires addressing the tension between local perceptions and actions, and the accomplishment of a global objective. In this work, we propose to learn decentralized controllers based solely on raw visual inputs. For the first time, this integrates the learning of two key components: communication and visual perception, in one end-to-end framework. More specifically, we consider that each robot has access to a visual perception of the immediate surroundings, and communication capabilities to transmit and receive messages from other neighboring robots. Our proposed learning framework combines a convolutional neural network (CNN) for each robot to extract messages from the visual inputs, and a graph neural network (GNN) over the entire swarm to transmit, receive and process these messages in order to decide on actions. The use of a GNN and locally-run CNNs results naturally in a decentralized controller. We jointly train the CNNs and the GNN so that each robot learns to extract messages from the images that are adequate for the team as a whole. Our experiments demonstrate the proposed architecture in the problem of drone flocking and show its promising performance and scalability, e.g., achieving successful decentralized flocking for large-sized swarms.

Algebraic neural networks (AlgNNs) are composed of a cascade of layers each one associated to and algebraic signal model, and information is mapped between layers by means of a nonlinearity function. AlgNNs provide a generalization of neural network architectures where formal convolution operators are used, like for instance traditional neural networks (CNNs) and graph neural networks (GNNs). In this paper we study stability of AlgNNs on the framework of algebraic signal processing. We show how any architecture that uses a formal notion of convolution can be stable beyond particular choices of the shift operator, and this stability depends on the structure of subsets of the algebra involved in the model. We focus our attention on the case of algebras with a single generator.

Network data can be conveniently modeled as a graph signal, where data values are assigned to the nodes of a graph describing the underlying network topology. Successful learning from network data requires methods that effectively exploit this graph structure. Graph neural networks (GNNs) provide one such method and have exhibited promising performance on a wide range of problems. Understanding why GNNs work is of paramount importance, particularly in applications involving physical networks. We focus on the property of discriminability and establish conditions under which the inclusion of pointwise nonlinearities to a stable graph filter bank leads to an increased discriminative capacity for high-eigenvalue content. We define a notion of discriminability tied to the stability of the architecture, show that GNNs are at least as discriminative as linear graph filter banks, and characterize the signals that cannot be discriminated by either.

Graph convolutional neural networks (GCNNs) learn compositional representations from network data by nesting linear graph convolutions into nonlinearities. In this work, we approach GCNNs from a state-space perspective revealing that the graph convolutional module is a minimalistic linear state-space model, in which the state update matrix is the graph shift operator. We show that this state update may be problematic because it is nonparametric, and depending on the graph spectrum it may explode or vanish. Therefore, the GCNN has to trade its degrees of freedom between extracting features from data and handling these instabilities. To improve such trade-off, we propose a novel family of nodal aggregation rules that aggregate node features within a layer in a nonlinear state-space parametric fashion allowing for a better trade-off. We develop two architectures within this family inspired by the recurrence with and without nodal gating mechanisms. The proposed solutions generalize the GCNN and provide an additional handle to control the state update and learn from the data. Numerical results on source localization and authorship attribution show the superiority of the nonlinear state-space generalization models over the baseline GCNN.

Graph neural networks (GNNs) are learning architectures that rely on knowledge of the graph structure to generate meaningful representations of large-scale network data. GNN stability is thus important as in real-world scenarios there are typically uncertainties associated with the graph. We analyze GNN stability using kernel objects called graphons. Graphons are both limits of convergent graph sequences and generating models for deterministic and stochastic graphs. Building upon the theory of graphon signal processing, we define graphon neural networks and analyze their stability to graphon perturbations. We then extend this analysis by interpreting the graphon neural network as a generating model for GNNs on deterministic and stochastic graphs instantiated from the original and perturbed graphons. We observe that GNNs are stable to graphon perturbations with a stability bound that decreases asymptotically with the size of the graph. This asymptotic behavior is further demonstrated in an experiment of movie recommendation.

We consider optimal resource allocation problems under asynchronous wireless network setting. Without explicit model knowledge, we design an unsupervised learning method based on Aggregation Graph Neural Networks (Agg-GNNs). Depending on the localized aggregated information structure on each network node, the method can be learned globally and asynchronously while implemented locally. We capture the asynchrony by modeling the activation pattern as a characteristic of each node and train a policy-based power allocation method. We also propose a permutation invariance property which indicates the transferability of the trained Agg-GNN. We finally verify our strategy by numerical simulations compared with baseline methods.

Many algorithms for control of multi-robot teams operate under the assumption that low-latency, global state information necessary to coordinate agent actions can readily be disseminated among the team. However, in harsh environments with no existing communication infrastructure, robots must form ad-hoc networks, forcing the team to operate in a distributed fashion. To overcome this challenge, we propose a task-agnostic, decentralized, low-latency method for data distribution in ad-hoc networks using Graph Neural Networks (GNN). Our approach enables multi-agent algorithms based on global state information to function by ensuring it is available at each robot. To do this, agents glean information about the topology of the network from packet transmissions and feed it to a GNN running locally which instructs the agent when and where to transmit the latest state information. We train the distributed GNN communication policies via reinforcement learning using the average Age of Information as the reward function and show that it improves training stability compared to task-specific reward functions. Our approach performs favorably compared to industry-standard methods for data distribution such as random flooding and round robin. We also show that the trained policies generalize to larger teams of both static and mobile agents.

The multi-robot coverage problem is an essential building block for systems that perform tasks like inspection, exploration, or search and rescue. We discretize the coverage problem to induce a spatial graph of locations and represent robots as nodes in the graph. Then, we train a Graph Neural Network controller that leverages the spatial equivariance of the task to imitate an expert open-loop routing solution. This approach generalizes well to much larger maps and larger teams that are intractable for the expert. In particular, the model generalizes effectively to a simulation of ten quadrotors and dozens of buildings in an urban setting. We also demonstrate the GNN controller can surpass planning-based approaches in an exploration task.

Deterministic policies demonstrate substantial empirical success over their stochastic counterparts as they remove a level of randomness in Policy Gradient (PG) methods when applied to stochastic search problems involving Markov decision processes. However, current implementations require the use of state-action value ($Q$-function) approximators, also known as critics, to obtain estimates of the associated policy-reward gradient. In this work, we propose the use of two-point stochastic evaluations to obtain gradient estimates of a smoothed$Q$-function surrogate, constructed by evaluating pairs of the$Q$-function at low-dimensional, randomized initial action perturbations. This procedure lifts the dependence on a critic and restores true model-free policy learning, and with provable algorithmic stability. In fact, our finite complexity bounds improve upon existing results by up to 2 orders of magnitude in terms of iteration complexity, and by up to 3/2 orders of magnitude in terms of sample complexity. Simulation results on an agent navigation problem showcase the effectiveness of our proposed algorithm in a practical setting, as well.

Despite strong performance in numerous applications, the fragility of deep learning to input perturbations has raised serious questions about its use in safety-critical domains. While adversarial training can mitigate this issue in practice, state-of-the-art methods are increasingly application-dependent, heuristic in nature, and suffer from fundamental trade-offs between nominal performance and robustness. Moreover, the problem of finding worst-case perturbations is non-convex and underparameterized, both of which engender a non-favorable optimization landscape. Thus, there is a gap between the theory and practice of robust learning, particularly with respect to when and why adversarial training works. In this paper, we take a constrained learning approach to address these questions and to provide a theoretical foundation for robust learning. In particular, we leverage semi-infinite optimization and non-convex duality theory to show that adversarial training is equivalent to a statistical problem over perturbation distributions. Notably, we show that a myriad of previous robust training techniques can be recovered for particular, sub-optimal choices of these distributions. Using these insights, we then propose a hybrid Langevin Markov Chain Monte Carlo approach for which several common algorithms (e.g., PGD) are special cases. Finally, we show that our approach can mitigate the trade-off between nominal and robust performance, yielding state-of-the-art results on MNIST and CIFAR-10. Our code is available at: https://github.com/arobey1/advbench.

Graph neural networks (GNNs) are information processing architectures for signals supported on graphs. They are presented here as generalizations of convolutional neural networks (CNNs) in which individual layers contain banks of graph convolutional filters instead of banks of classical convolutional filters. Otherwise, GNNs operate as CNNs. Filters are composed of pointwise nonlinearities and stacked in layers. It is shown that GNN architectures exhibit equivariance to permutation and stability to graph deformations. These properties help explain the good performance of GNNs that can be observed empirically. It is also shown that if graphs converge to a limit object, a graphon, GNNs converge to a corresponding limit object, a graphon neural network. This convergence justifies the transferability of GNNs across networks with different numbers of nodes. Concepts are illustrated by the application of GNNs to recommendation systems, decentralized collaborative control, and wireless communication networks.

In this paper, we propose a Distributed Accumulated Newton Conjugate gradiEnt (DANCE) method in which sample size is gradually increasing to quickly obtain a solution whose empirical loss is under satisfactory statistical accuracy. Our proposed method is multistage in which the solution of a stage serves as a warm start for the next stage which contains more samples (including the samples in the previous stage). The proposed multistage algorithm reduces the number of passes over data to achieve the statistical accuracy of the full training set. Moreover, our algorithm in nature is easy to be distributed and shares the strong scaling property indicating that acceleration is always expected by using more computing nodes. Various iteration complexity results regarding descent direction computation, communication efficiency and stopping criteria are analyzed under convex setting. Our numerical results illustrate that the proposed method outperforms other comparable methods for solving learning problems including neural networks.

This paper investigates the optimal resource allocation in free space optical (FSO) fronthaul networks. The optimal allocation maximizes an average weighted sum-capacity subject to power limitation and data congestion constraints. Both adaptive power assignment and node selection are considered based on the instantaneous channel state information (CSI) of the links. By parameterizing the resource allocation policy, we formulate the problem as an unsupervised statistical learning problem. We consider the graph neural network (GNN) for the policy parameterization to exploit the FSO network structure with small-scale training parameters. The GNN is shown to retain the permutation equivariance that matches with the permutation equivariance of resource allocation policy in networks. The primal-dual learning algorithm is developed to train the GNN in a model-free manner, where the knowledge of system models is not required. Numerical simulations present the strong performance of the GNN relative to a baseline policy with equal power assignment and random node selection.

This paper is concerned with the study of constrained statistical learning problems, the unconstrained version of which are at the core of virtually all of modern information processing. Accounting for constraints, however, is paramount to incorporate prior knowledge and impose desired structural and statistical properties on the solutions. Still, solving constrained statistical problems remains challenging and guarantees scarce, leaving them to be tackled using regularized formulations. Though practical and effective, selecting regularization parameters so as to satisfy requirements is challenging, if at all possible, due to the lack of a straightforward relation between parameters and constraints. In this work, we propose to directly tackle the constrained statistical problem overcoming its infinite dimensionality, unknown distributions, and constraints by leveraging finite dimensional parameterizations, sample averages, and duality theory. Aside from making the problem tractable, these tools allow us to bound the empirical duality gap, i.e., the difference between our approximate tractable solutions and the actual solutions of the original statistical problem. We demonstrate the effectiveness and usefulness of this constrained formulation in a fair learning application.

We consider the problem of finding optimal power allocations subject to system constraints in ad-hoc wireless networks. The resulting optimization problem has the form of a constrained learning problem, motivating the use of a function parameterization such as a neural network. While such a policy can be trained with a primal-dual learning method, traditional neural network architectures are unsuitable for execution in wireless networks, as such networks change frequently in practice, rendering the learned neural network ineffective. To learn a transferable policy that can generalize to varying and growing networks, we propose the use of so-called random edge graph neural networks (REGNNs). Such REG-NNs are shown to exhibit an essential permutation invariance property for the power allocation problem that suggest transference capabilities. In numerical simulations, we validate this suggestion by showing how REGNNs trained on a single ad-hoc network outperform baselines in new randomly drawn networks of growing size.

Graph neural networks (GNNs), consisting of a cascade of layers applying a graph convolution followed by a pointwise nonlinearity, have become a powerful architecture to process signals supported on graphs. Graph convolutions (and thus, GNNs), rely heavily on knowledge of the graph for operation. However, in many practical cases the graph shift operator (GSO) is not known and needs to be estimated, or might change from training time to testing time. In this paper, we are set to study the effect that a change in the underlying graph topology that supports the signal has on the output of a GNN. We prove that graph convolutions with integral Lipschitz filters lead to GNNs whose output change is bounded by the size of the relative change in the topology. Furthermore, we leverage this result to show that the main reason for the success of GNNs is that they are stable architectures capable of discriminating features on high eigenvalues, which is a feat that cannot be achieved by linear graph filters (which are either stable or discriminative, but cannot be both). Finally, we comment on the use of this result to train GNNs with increased stability and run experiments on movie recommendation systems.

Graph neural networks (GNNs) model nonlinear representations in graph data with applications in distributed agent coordination, control, and planning among others. However, current GNN implementations assume ideal distributed scenarios and ignore link fluctuations that occur due to environment or human factors. In these situations, the GNN fails to address its distributed task if the topological randomness is not considered accordingly. To overcome this issue, we put forth the stochastic graph neural network (SGNN) model: a GNN where the distributed graph convolutional operator is modified to account for the network changes. Since stochasticity brings in a new paradigm, we develop a novel learning process for the SGNN and introduce the stochastic gradient descent (SGD) algorithm to estimate the parameters. We prove through the SGD that the SGNN learning process converges to a stationary point under mild Lipschitz assumptions. Numerical simulations corroborate the proposed theory and show an improved performance of the SGNN compared with the conventional GNN when operating over random time varying graphs.

Stochastic gradient descent is a canonical tool for addressing stochastic optimization problems, and forms the bedrock of modern machine learning and statistics. In this work, we seek to balance the fact that attenuating step-sizes is required for exact asymptotic convergence with the fact that larger constant step-sizes learn faster in finite time up to an error. To do so, rather than fixing the mini-batch and step-size at the outset, we propose a strategy to allow parameters to evolve adaptively. Specifically, the batch-size is set to be a piecewise-constant increasing sequence where the increase occurs when a suitable error criterion is satisfied. Moreover, the step-size is selected as that which yields the fastest convergence. The overall algorithm, two scale adaptive (TSA) scheme, is shown to inherit the exact asymptotic convergence of stochastic gradient method. More importantly, the optimal error decreasing rate is achieved theoretically, as well as an overall reduction in sample computational cost. Experimentally, we observe a favorable tradeoff relative to standard SGD schemes absorbing their advantages, which illustrates the significant performance of proposed TSA scheme.

Despite the simplicity and intuitive interpretation of minimum mean squared error (MMSE) estimators, their effectiveness in certain scenarios is questionable. Indeed, minimizing squared errors on average does not provide any form of stability, as the volatility of the estimation error is left unconstrained. When this volatility is statistically significant, the difference between the average and realized performance of the MMSE estimator can be drastically different. To address this issue, we introduce a new risk-aware MMSE formulation which trades between mean performance and risk by explicitly constraining the expected predictive variance of the involved squared error. We show that, under mild moment boundedness conditions, the corresponding risk-aware optimal solution can be evaluated explicitly, and has the form of an appropriately biased nonlinear MMSE estimator. We further illustrate the effectiveness of our approach via several numerical examples, which also showcase the advantages of risk-aware against risk-neutral MMSE estimation, especially in models involving skewed, heavy-tailed distributions.

Optimal resource allocation in real-world wireless systems is rather challenging, not only due to the unavailability of accurate statistical channel models, but also because expressions of maximal or achievable information rates are most often unknown, or not adequately precise. Under a modular stochastic functional optimization framework, we propose a new zeroth-order stochastic primal-dual algorithm for completely data-driven, model-free and gradient-free learning of optimal resource allocation policies for ergodic network optimization. Our contribution relies on Gaussian smoothing of the corresponding constrained policy search problem, and on the representation power of universal policy parameterizations, such as Deep Neural Networks (DNNs). Indeed, our simulations demonstrate that DNN-based policies produced by the proposed primal-dual method attain near-ideal performance, based exclusively on limited channel probing, completely bypassing the need for gradient computations, and at the absence of channel or information rate models.

Optimal power flow (OPF) is one of the most important optimization problems in the energy industry. In its simplest form, OPF attempts to find the optimal power that the generators within the grid have to produce to satisfy a given demand. Optimality is measured with respect to the cost that each generator incurs in producing this power. The OPF problem is non-convex due to the sinusoidal nature of electrical generation and thus is difficult to solve. Using small angle approximations leads to a convex problem known as DC OPF, but this approximation is no longer valid when power grids are heavily loaded. Many approximate solutions have been since put forward, but these do not scale to large power networks. In this paper, we propose using graph neural networks (which are localized, scalable parametrizations of network data) trained under the imitation learning framework to approximate a given optimal solution. While the optimal solution is costly, it is only required to be computed for network states in the training set. During test time, the GNN adequately learns how to compute the OPF solution. Numerical experiments are run on the IEEE-30 and IEEE-118 test cases.

In federated learning, a centralized model is realized based on information received from a group of agents each collecting data. This setting has two major challenges: the agents observe data over different distributions and they have only limited capabilities of sending data over the network to the centralized unit. Therefore, sending all the training data over the network is impractical. Each agent must train its own model and decide what relevant information it needs to send to the centralized unit. In this work we propose a method for federated learning in which each agent learns a low complexity Reproducing kernel Hilbert space representation. Leveraging the zero duality gap and the fact that each dual variable is associated with a sample, the agent discards samples for which the optimal dual variable is zero and sends only fundamental samples to the centralized unit. The centralized unit then computes the global model. We show that as the sample size grows, the solution obtained by the central unit converges to that obtained by an omniscient classifier which has access to all samples from all agents. We illustrate the performance of our federated learning algorithm and compare it to the omniscient classifier with a simulation.

In many network problems, graphs may change by the addition of nodes, or the same problem may need to be solved in multiple similar graphs. This generates inefficiency, as analyses and systems that are not transferable have to be redesigned. To address this, we consider graphons, which are both limit objects of convergent graph sequences and random graph models. We define graphon signals and introduce the Graphon Fourier Transform (WFT), to which the Graph Fourier Transform (GFT) is shown to converge. This result is demonstrated in two numerical experiments where, as expected, the GFT converges, hinting to the possibility of centralizing analysis and design on graphons to leverage transferability.

Graph Recurrent Neural Networks (GRNNs) are a neural network architecture devised to learn from graph processes, which are time sequences of graph signals. Similarly to traditional recurrent neural networks, GRNNs experience the problem of vanishing/exploding gradients when learning long term causal dependencies. When these dependencies do not depend on the graph, this issue is solved by the addition of time gates (long short-term memory architectures). However, in graph processes long term dependencies are directly influenced by the graph structure, and can be stronger or weaker across certain node paths. To address this, we propose two spatial gating strategies for GRNNs leveraging the node and edge structure of the graph. Node and edgegated GRNNs are shown to outperform other GRNNs in a synthetic as well as a real-world problem of earthquake epicenter prediction.

In this paper, we consider the problem of projecting networks onto metric spaces. Networks are structures that encode relationships between pairs of elements or nodes. However, these relationships can be independent of each other, and need not be defined for every pair of nodes. This is in contrast to a metric space, which requires that a distance between every pair of elements in the space be defined. To understand how to project networks onto metric spaces, we take an axiomatic approach: we first state two axioms for projective maps from the set of all networks to the set of finite metric spaces, then show that only one projection satisfies these requirements. The developed technique is shown to be an effective method for finding approximate solutions to combinatorial optimization problems. Finally, we illustrate the use of metric trees for efficient search in projected networks.

We consider the problem of allocating 5G radio resources over wireless communication links to control a series of independent low-latency wireless control systems common in industrial settings. Each control system sends state information to the base station to compute control signals under tight latency requirements. Such latency requirements can be met by restricting the uplink traffic to a single subframe in each 5G frame, thus ensuring a millisecond latency bound while leaving the remaining subframes available for scheduling overhead and coexisting broadband traffic. A linear assignment problem can be formulated to minimize the expected number of packet drops, but this alone is not sufficient to achieve good performance. We propose an optimal scheduling with respect to a control operation cost that allocates resources based on current control system needs. The resulting control-aware scheduling method is tested in simulation experiments that show drastically improved performance in 5G settings relative to control-agnostic scheduling under the proposed time-sliced frame structure.

In this work, we introduce Mobile Wireless Infrastructure on Demand: a framework for providing wireless connectivity to multi-robot teams via autonomously reconfiguring ad-hoc networks. In many cases, previous multi-agent systems either assumed the availability of existing communication infrastructure or were required to create a network in addition to completing their objective. Instead our system explicitly assumes the responsibility of creating and sustaining a wireless network capable of satisfying end-to-end communication requirements of a team of agents, called the task team, performing an arbitrary objective. To accomplish this goal, we propose a joint optimization framework that alternates between finding optimal network routes to support data flows between the task agents and improving the performance of the network by repositioning a collection of mobile relay nodes referred to as the network team. We demonstrate our approach with simulations and experiments wherein wireless connectivity is provided to patrolling task agents.

Modeling how a robot interacts with the environment around it is an important prerequisite for designing control and planning algorithms. In fact, the performance of controllers and planners is highly dependent on the quality of the model. One popular approach is to learn data driven models in order to compensate for inaccurate physical measurements and to adapt to systems that evolve over time. In this paper, we investigate a method to regularize model learning techniques to provide better error characteristics for traditional control and planning algorithms. This work proposes learning "Sufficiently Accurate" models of dynamics using a primal-dual method that can explicitly enforce constraints on the error in pre-defined parts of the state-space. The result of this method is that the error characteristics of the learned model is more predictable and can be better utilized by planning and control algorithms. The characteristics of Sufficiently Accurate models are analyzed through experiments on a simulated ball paddle system.

Effective communication is key to successful, decentralized, multi-robot path planning. Yet, it is far from obvious what information is crucial to the task at hand, and how and when it must be shared among robots. To side-step these issues and move beyond hand-crafted heuristics, we propose a combined model that automatically synthesizes local communication and decision-making policies for robots navigating in constrained workspaces. Our architecture is composed of a convolutional neural network (CNN) that extracts adequate features from local observations, and a graph neural network (GNN) that communicates these features among robots. We train the model to imitate an expert algorithm, and use the resulting model online in decentralized planning involving only local communication and local observations. We evaluate our method in simulations by navigating teams of robots to their destinations in 2D cluttered workspaces. We measure the success rates and sum of costs over the planned paths. The results show a performance close to that of our expert algorithm, demonstrating the validity of our approach. In particular, we show our model's capability to generalize to previously unseen cases (involving larger environments and larger robot teams).

As learning solutions reach critical applications in social, industrial, and medical domains, the need to curtail their behavior has become paramount. There is now ample evidence that without explicit tailoring, learning can lead to biased, unsafe, and prejudiced solutions. To tackle these problems, we develop a generalization theory of constrained learning based on the probably approximately correct (PAC) learning framework. In particular, we show that imposing requirements does not make a learning problem harder in the sense that any PAC learnable class is also PAC constrained learnable using a constrained counterpart of the empirical risk minimization (ERM) rule. For typical parametrized models, however, this learner involves solving a constrained non-convex optimization program for which even obtaining a feasible solution is challenging. To overcome this issue, we prove that under mild conditions the empirical dual problem of constrained learning is also a PAC constrained learner that now leads to a practical constrained learning algorithm based solely on solving unconstrained problems. We analyze the generalization properties of this solution and use it to illustrate how constrained learning can address problems in fair and robust classification.

Graph neural networks (GNNs) rely on graph convolutions to extract local features from network data. These graph convolutions combine information from adjacent nodes using coefficients that are shared across all nodes. Since these coefficients are shared and do not depend on the graph, one can envision using the same coefficients to define a GNN on another graph. This motivates analyzing the transferability of GNNs across graphs. In this paper we introduce graphon NNs as limit objects of GNNs and prove a bound on the difference between the output of a GNN and its limit graphon-NN. This bound vanishes with growing number of nodes if the graph convolutional filters are bandlimited in the graph spectral domain. This result establishes a tradeoff between discriminability and transferability of GNNs.

In this paper, we consider the problem of computing the barycenter of a set of probability distributions under the Sinkhorn divergence. This problem has recently found applications across various domains, including graphics, learning, and vision, as it provides a meaningful mechanism to aggregate knowledge. Unlike previous approaches which directly operate in the space of probability measures, we recast the Sinkhorn barycenter problem as an instance of unconstrained functional optimization and develop a novel functional gradient descent method named \texttt{Sinkhorn Descent} (\texttt{SD}). We prove that \texttt{SD} converges to a stationary point at a sublinear rate, and under reasonable assumptions, we further show that it asymptotically finds a global minimizer of the Sinkhorn barycenter problem. Moreover, by providing a mean-field analysis, we show that \texttt{SD} preserves the {weak convergence} of empirical measures. Importantly, the computational complexity of \texttt{SD} scales linearly in the dimension $d$ and we demonstrate its scalability by solving a $100$-dimensional Sinkhorn barycenter problem.

We consider the problem of minimizing a functional over a parametric family of probability measures, where the parameterization is characterized via a push-forward structure. An important application of this problem is in training generative adversarial networks. In this regard, we propose a novel Sinkhorn Natural Gradient (SiNG) algorithm which acts as a steepest descent method on the probability space endowed with the Sinkhorn divergence. We show that the Sinkhorn information matrix (SIM), a key component of SiNG, has an explicit expression and can be evaluated accurately in complexity that scales logarithmically with respect to the desired accuracy. This is in sharp contrast to existing natural gradient methods that can only be carried out approximately. Moreover, in practical applications when only Monte-Carlo type integration is available, we design an empirical estimator for SIM and provide the stability analysis. In our experiments, we quantitatively compare SiNG with state-of-the-art SGD-type solvers on generative tasks to demonstrate its efficiency and efficacy of our method.

We consider learning problems over training sets in which both, the number of training examples and the dimension of the feature vectors, are large. To solve these problems we propose the random parallel stochastic algorithm (RAPSA). We call the algorithm random parallel because it utilizes multiple parallel processors to operate on a randomly chosen subset of blocks of the feature vector. RAPSA is doubly stochastic since each processor utilizes a random set of functions to compute the stochastic gradient associated with a randomly chosen sets of variable coordinates. Algorithms that are parallel in either of these dimensions exist, but RAPSA is the first attempt at a methodology that is parallel in both the selection of blocks and the selection of elements of the training set. In RAPSA, processors utilize the randomly chosen functions to compute the stochastic gradient component associated with a randomly chosen block. The technical contribution of this paper is to show that this minimally coordinated algorithm converges to the optimal classifier when the training objective is strongly convex. Moreover, we present an accelerated version of RAPSA (ARAPSA) that incorporates the objective function curvature information by premultiplying the descent direction by a Hessian approximation matrix. We further extend the results for asynchronous settings and show that if the processors perform their updates without any coordination the algorithms are still convergent to the optimal argument. RAPSA and its extensions are then numerically evaluated on a linear estimation problem and a binary image classification task using the MNIST handwritten digit dataset.

Large-scale data science trains models for data sets containing massive numbers of samples. Training is often formulated as the solution of empirical risk minimization problems that are optimization programs whose complexity scales with the number of elements in the data set. Stochastic optimization methods overcome this challenge, but they come with their own set of limitations. This article discusses recent developments to accelerate the convergence of stochastic optimization through the exploitation of second-order information. This is achieved with stochastic variants of quasi-Newton methods that approximate the curvature of the objective function using stochastic gradient information. The reasons for why this leads to faster convergence are discussed along with the introduction of an incremental method that exploits memory to achieve a superlinear convergence rate. This is the best-known convergence rate for a stochastic optimization method. Stochastic quasi-Newton methods are applied to several problems, including prediction of the click-through rate of an advertisement displayed in response to a specific search engine query by a specific visitor. Experimental evaluations showcase reductions in overall computation time relative to stochastic gradient descent algorithms.

Radio on Free Space Optics (RoFSO), as a universal platform for heterogeneous wireless services, is able to transmit multiple radio frequency signals at high rates in free space optical networks. This paper investigates the optimal design of power allocation for Wavelength Division Multiplexing (WDM) transmission in RoFSO systems. The proposed problem is a weighted total capacity maximization problem with two constraints of total power limitation and eye safety concern. The model-based Stochastic Dual Gradient algorithm is presented first, which solves the problem exactly by exploiting the null duality gap. The model-free Primal-Dual Deep Learning algorithm is then developed to learn and optimize the power allocation policy with Deep Neural Network (DNN) parametrization, which can be utilized without any knowledge of system models. Numerical simulations are performed to exhibit significant performance of our algorithms compared to the average equal power allocation.

Sparse modeling seeks to represent signals as a linear combination of a small number of atoms from an overparametrized dictionary. Despite the success of these linear models, they can be too restrictive for applications involving nonlinear measurements. Using nonlinear atoms, however, poses an additional obstacle to the sparse recovery problem, since it remains non-convex even after relaxing the sparsity objective (e.g., using atomic norms). We address this issue in the context of continuous dictionaries by posing nonlinear sparse recovery as a sparse functional program that explicitly minimizes the functional equivalent of the "ℓ0-norm," i.e., the function support measure. By proving that strong duality holds for these optimization problems, we show that nonlinear sparse recovery over continuous dictionaries precludes relaxations since it may be solved efficiently using duality. This result is non-parametric, in that it does not assume the data follows the measurement model, and does not require incoherence assumptions, such as the restricted isometry/eigenvalue property. We also use strong duality to derive a relation between minimizing the support of a function and minimizing its L1-norm, although this does not imply that the latter leads to sparse solutions. We illustrate this new approach in a nonlinear line spectrum estimation problem.

We consider the problem of allocating radio resources over wireless communication links to control a series of independent low-latency wireless control systems common in industrial settings. Supporting wireless control in time sensitive settings requires fast data rates over wireless links, which comes at the cost of reliability. It is challenging to meet both latency and reliability requirements with an equal or arbitrary allocation of resources. We thus propose a novel control-aware approach to the low-latency scheduling problem in which we incorporate control and channel state information in allocating bandwidth and data rates across the wireless links. Control systems that are in desirable states are given modest requirements on error rates, while systems in undesirable states are given more priority. We derive control-aware packet error rate targets for each system to satisfy stability goals and make scheduling decisions to meet such targets while reducing total transmission time. The resulting control-aware based method is tested in simulation experiments that demonstrate its effectiveness in meeting control-based goals under tight latency constraints relative to control-agnostic scheduling.

We consider the problem of finding optimal resource allocations subject to system constraints in a generic class of problems in wireless communications. These problems are inherently challenging due to functional optimization and potential non-convexities. However, these problems can be observed to take the form of a regression problem, although one in which the statistical loss function appears as a constraint. This motivates the use of machine learning model parameterizations. To apply gradient-based solution algorithms that do not require model knowledge, we convert the constrained optimization problem to an unconstrained one using Lagrangian duality. Despite the non-convexity in the problem, we formally show that the sub-optimality of the dual domain problem is small when the learning parameterization is sufficiently dense. We then present a primal-dual learning algorithm that looks for solutions to the dual problem using model-free gradient estimates. In a numerical simulation, we demonstrate the near-optimality of the proposed model-free algorithm using a neural network parametrization for a capacity maximization problem.

Graph neural networks (GNNs) regularize classical neural networks by exploiting the underlying irregular structure supporting graph data, extending its application to broader data domains. The aggregation GNN presented here is a novel GNN that exploits the fact that the data collected at a single node by means of successive local exchanges with neighbors exhibits a regular structure. Thus, regular convolution and regular pooling yield an appropriately regularized GNN. To address some scalability issues that arise when collecting all the information at a single node, we propose a multi-node aggregation GNN that constructs regional features that are later aggregated into more global features and so on. We show superior performance in a source localization problem on synthetic graphs and on the authorship attribution problem.

Reproducing kernel ilbert spaces (RKHSs) have been at the core of successful non-parametric tools in signal processing, statistics, and machine learning. Despite their success, the computational complexity of these models often hinders their use in practice. Indeed, fitting RKHS models typically relies on representer theorems to express the solution space as a combination of kernels evaluated at the training samples. Thus, the computational cost of evaluating these models is proportional to the number of training samples, which in many applications is prohibitively high. This issue is often addressed by sparsifying the coefficients of the kernel expansion, despite the fact that classical representer theorems no longer hold in the presence of sparsity penalties. In this work, we propose to directly tackle sparse learning over RKHSs by posing it as a functional problem. In other words, by formulating the RKHS model as a sparse, continuous combination of atoms from an overparametrized, continuous dictionary containing the value of the kernel evaluated at every point of the function domain. We show that despite the infinite dimensionality and non-convexity of the underlying optimization problem, these models can be fit exactly and efficiently using duality. We illustrate the performance of this technique in numerical experiments.

Graph neural networks (GNNs) have been shown to replicate convolutional neural networks' (CNNs) superior performance in many problems involving graphs. By replacing regular convolutions with linear shift-invariant graph filters (LSI-GFs), GNNs take into account the (irregular) structure of the graph and provide meaningful representations of network data. However, LSI-GFs fail to encode local nonlinear graph signal behavior, and so do regular activation functions, which are nonlinear but pointwise. To address this issue, we propose median activation functions with support on graph neighborhoods instead of individual nodes. A GNN architecture with a trainable multirresolution version of this activation function is then tested on synthetic and real-word datasets, where we show that median activation functions can improve GNN capacity with marginal increase in complexity.

Reducing the variance of estimators for policy gradient has long been the focus of reinforcement learning research. While classic algorithms like REINFORCE find an $\epsilon$-approximate first-order stationary point in $\OM({1}/{\epsilon^4})$ random trajectory simulations, no provable improvement on the complexity has been made so far. This paper presents a Hessian aided policy gradient method with the first improved sample complexity of $\OM({1}/{\epsilon^3})$. While our method exploits information from the policy Hessian, it can be implemented in linear time with respect to the parameter dimension and is hence applicable to sophisticated DNN parameterization. Simulations on standard tasks validate the efficiency of our method.

In this paper, we present a learning approach to goal assignment and trajectory planning for unlabeled robots operating in 2D, obstacle-filled workspaces. More specifically, we tackle the unlabeled multi-robot motion planning problem with motion constraints as a multi-agent reinforcement learning problem with some sparse global reward. In contrast with previous works, which formulate an entirely new hand-crafted optimization cost or trajectory generation algorithm for a different robot dynamic model, our framework is a general approach that is applicable to arbitrary robot models. Further, by using the velocity obstacle, we devise a smooth projection that guarantees collision free trajectories for all robots with respect to their neighbors and obstacles. The efficacy of our algorithm is demonstrated through varied simulations. A video describing our method and results can be found here.

We envision a system that concisely describes the rules of air traffic control, assists human operators and supports dense autonomous air traffic around commercial airports. We develop a method to learn the rules of air traffic control from real data as a cost function via maximum entropy inverse reinforcement learning. This cost function is used as a penalty for a search-based motion planning method that discretizes both the control and the state space. We illustrate the methodology by showing that our approach can learn to imitate the airport arrival routes and separation rules of dense commercial air traffic. The resulting trajectories are shown to be safe, feasible, and efficient.

Scattering transforms are non-trainable deep convolutional architectures that exploit the multi-scale resolution of a wavelet filter bank to obtain an appropriate representation of data. More importantly, they are proven invariant to translations, and stable to perturbations that are close to translations. This stability property dons the scattering transform with a robustness to small changes in the metric domain of the data. When considering network data, regular convolutions do not hold since the data domain presents an irregular structure given by the network topology. In this work, we extend scattering transforms to network data by using multi-resolution graph wavelets, whose computation can be obtained by means of graph convolutions. Furthermore, we prove that the resulting graph scattering transforms are stable to metric perturbations of the underlying network. This renders graph scattering transforms robust to changes on the network topology, making it particularly useful for cases of transfer learning, topology estimation or time-varying graphs.

Autonomous agents must often deal with conflicting requirements, such as completing tasks using the least amount of time/energy, learning multiple tasks, or dealing with multiple opponents. In the context of reinforcement learning~(RL), these problems are addressed by (i)~designing a reward function that simultaneously describes all requirements or (ii)~combining modular value functions that encode them individually. Though effective, these methods have critical downsides. Designing good reward functions that balance different objectives is challenging, especially as the number of objectives grows. Moreover, implicit interference between goals may lead to performance plateaus as they compete for resources, particularly when training on-policy. Similarly, selecting parameters to combine value functions is at least as hard as designing an all-encompassing reward, given that the effect of their values on the overall policy is not straightforward. The later is generally addressed by formulating the conflicting requirements as a constrained RL problem and solved using Primal-Dual methods. These algorithms are in general not guaranteed to converge to the optimal solution since the problem is not convex. This work provides theoretical support to these approaches by establishing that despite its non-convexity, this problem has zero duality gap, i.e., it can be solved exactly in the dual domain, where it becomes convex. Finally, we show this result basically holds if the policy is described by a good parametrization~(e.g., neural networks) and we connect this result with primal-dual algorithms present in the literature and we establish the convergence to the optimal solution.

We consider the problem of allocating radio resources over wireless communication links to control a series of independent wireless control systems. Low-latency transmissions are necessary in enabling time-sensitive control systems with high sampling rates to operate over wireless links. Enabling low-latency through fast data rates comes at the cost of reliability in the form of higher packet error rates due to channel noise. However, the impact of such communication link errors on the control system performance depends dynamically on the control system state. We propose a novel control-aware communication design to the low-latency resource allocation problem. In our proposed method, we incorporate both control and channel state information in scheduling transmissions across time slots, frequency bands, and data rates using the next-generation Wi-Fi scheduling architecture. Control systems that are closer to instability or further from a desired range in a given control cycle are given higher packet delivery rate targets to meet. Rather than a simple priority ranking, we derive precise adaptive packet error rate targets for each system needed to satisfy control-specific performance requirements. We use these adaptive rate targets to make scheduling decisions that reduce total transmission time. The resulting control-aware low-latency scheduling (CALLS) method is tested in numerous simulation experiments that demonstrate its effectiveness in meeting control-based goals under tight latency constraints relative to control-agnostic scheduling.

Despite their attractiveness, popular perception is that techniques for nonparametric function approximation do not scale to streaming data due to an intractable growth in the amount of storage they require. To solve this problem in a memory-affordable way, we propose an online technique based on functional stochastic gradient descent in tandem with supervised sparsification based on greedy function subspace projections. The method, called parsimonious online learning with kernels (POLK), provides a controllable tradeoff between its solution accuracy and the amount of memory it requires. We derive conditions under which the generated function sequence converges almost surely to the optimal function, and we establish that the memory requirement remains finite. We evaluate POLK for kernel multi-class logistic regression and kernel hinge-loss classification on three canonical data sets: a synthetic Gaussian mixture model, the MNIST hand-written digits, and the Brodatz texture database. On all three tasks, we observe a favorable trade-off of objective function evaluation, classification performance, and complexity of the nonparametric regressor extracted by the proposed method.

Most second order methods are inapplicable to large scale empirical risk minimization (ERM) problems because both, the number of samples N and number of parameters p are large. Large N makes it costly to evaluate Hessians and large p makes it costly to invert Hessians. This paper propose a novel adaptive sample size second-order method, which reduces the cost of computing the Hessian by solving a sequence of ERM problems corresponding to a subset of samples and lowers the cost of computing the Hessian inverse using a truncated eigenvalue decomposition. Although the sample size is grown at a geometric rate, it is shown that it is sufficient to run a single iteration in each growth stage to track the optimal classifier to within its statistical accuracy. This results in convergence to the optimal classifier associated with the whole set in a number of iterations that scales with $\log(N)$. The use of a truncated eigenvalue decomposition result in the cost of each iteration being of order $p^2$. Theoretical performance gains manifest in practical implementations.

Signal processing is rich in inherently continuous applications, such as radar, MRI, and source localization, in which sparsity priors play a key role in obtaining state-of-the-art results. To cope with the infinite dimensionality and non-convexity of these estimation problems, they are typically discretized and solved by means of convex relaxations, e.g., using atomic norms. Although successful, this approach is not without issues. Discretization often leads to high dimensional, potentially ill-conditioned optimization problems. Moreover, due to grid mismatch and other coherence issues, a sparse signal in the continuous domain may no longer be sparse when discretized. Finally, performance guarantees for atomic norm relaxations hold under assumptions that may be hard to meet in practice. We address these issues by directly tackling the continuous problem cast as a sparse functional optimization program. We prove that these problems have no duality gap and show that they can be solved efficiently using duality and a stochastic gradient ascent-type algorithm. We illustrate the performance of this new approach on a line spectral estimation problem.

This paper considers the resource allocation problem in wireless systems over an unknown time-varying non-stationary channel. The goal is to maximize a utility function, such as a capacity function, over a set of wireless nodes while satisfying a set of resource constraints. To bypass the need for a model for channel distribution as it varies over time, samples of the channel are taken at every time epoch to estimate the channel. The resulting stochastic optimization problem is converted in its Lagrange dual problem, where the resulting stochastic optimization problem can viewed equivalently as minimizing a certain empirical risk measure, a well-studied problem in machine learning. The second order Newton's method is used to quickly learn statistically approximated optimal resource allocation policies over the sampled dual function as the channel evolves over time epochs. The quadratic convergence rate of Newton is used to establish, under certain conditions on the sampling size and rate of channel variation, an instantaneous learning and tracking of these policies. Numerical simulations demonstrate the effectiveness of the learning algorithm on a low-dimensional wireless capacity maximization problem.

In this work, we jointly exploit tools from graph signal processing and control theory to drive a bandlimited graph signal that is being diffused on a random time-varying graph from a subset of nodes. As our main contribution, we rely only on the statistics of the graph to introduce the concept of controllability in the mean, and therefore drive the signal on the expected graph to a desired bandlimited state. A mean-square error (MSE) analysis is performed for two main tasks: i) to highlight the role played by the signal bandwidth and the control nodes to the deviation from the mean signal of a particular realization; and ii) to select the control nodes and design the control signal that minimize this MSE. Numerical results validate the introduced controllability in the mean framework and show its ability to cope with time-varying topologies.

Modern neuroimaging techniques offer disctinct views on brain structure and function. Data acquired using these techniques can be analyzed in terms of its network structure to identify organizing principles at the systems level. Graph representations are flexible frameworks where nodes are related to brain regions and edges to structural or functional links. Most research to date has focused on analyzing these graphs reflecting structure or function. Graph signal processing (GSP) is an emerging area of research where signals at the nodes are studied atop the underlying graph structure. Here, we review GSP tools for brain imaging data and discuss their potential to integrate brain structure with function. We discuss how brain activity can be meaningfully filtered. We also derive surrogate data as a null model to test significance for graph signals. We review that individuals with less concentration on graph high frequency could switch attention faster.

This paper develops new designs for recommender systems inspired by recent advances in graph signal processing. Recommender systems aim to predict unknown ratings by exploiting the information revealed in a subset of user-item observed ratings. Leveraging the notions of graph frequency and graph filters, we demonstrate that linear latent factor models, such as low-rank matrix completion, can be viewed as bandlimited interpolation algorithms that operate in a frequency domain given by the spectrum of a joint user and item network. This new interpretation paves the way to new methods for enhanced rating prediction. We propose a low complexity method by exploiting the eigenvector of correlation matrices constructed from known ratings. In the MovieLens 100k dataset, our designs reduce the root mean squared error compared to the ones in benchmark matrix completion by 0.6% and benchmark nearest neighbor methods by 4.2%.

We consider the problem of dictionary learning over training sets whose sample size and parameter dimension are large-scale, which is formulated as a non-convex stochastic program where the objective decomposes into a smooth non-convex part and a convex sparsity-promoting penalty. We propose a Doubly Stochastic Successive Convex approximation scheme (DSSC) as a new numerical tool to address this task which operates by decomposing the dictionary and sparse codes into blocks and operates on random subsets of blocks at each step. The algorithm belongs to the family of successive convex approximation methods since we replace the original non-convex stochastic objective by a strongly convex sample surrogate function, and solve the resulting convex program, for each randomly selected block in parallel. The method operates on subsets of features (block coordinate methods) and training examples (stochas-tic approximation) at each step. In contrast to many training schemes for dictionary learning, DSSC attains almost sure convergence to a stationary solution of the problem. We observe the practical benefits of this approach for stable learning and computational speedup when applied to streaming visual data gathered by a field robot.

In this paper, we propose a novel architecture and a self-supervised policy gradient algorithm, which employs unsupervised auxiliary tasks to enable a mobile robot to learn how to navigate to a given goal. The dependency on the global information is eliminated by providing only sparse range-finder measurements to the robot. The partially observable planning problem is addressed by splitting it into a hierarchical process. We use convolutional networks to plan locally, and a differentiable memory to provide information about past time steps in the trajectory. These modules, combined in our network architecture, produce globally consistent plans. The sparse reward problem is mitigated by our modified policy gradient algorithm. We model the robots uncertainty with unsupervised tasks to force exploration. The novel architecture we propose with the modified version of the policy gradient algorithm allows our robot to reach the goal in a sample efficient manner, which is orders of magnitude faster than the current state of the art policy gradient algorithm. Simulation and experimental results are provided to validate the proposed approach.

We present a reinforcement learning algorithm for learning sparse non-parametric controllers in a Reproducing Kernel Hilbert Space. We improve the sample complexity of this approach by imposing a structure of the state-action function through a normalized advantage function (NAF). This representation of the policy enables efficiently composing multiple learned models without additional training samples or interaction with the environment. We demonstrate the performance of this algorithm on learning obstacle-avoidance policies in multiple simulations of a robot equipped with a laser scanner while navigating in a 2D environment. We apply the composition operation to various policy combinations and test them to show that the composed policies retain the performance of their components. We also transfer the composed policy directly to a physical platform operating in an arena with obstacles in order to demonstrate a degree of generalization.

Modern neuroimaging techniques provide us with unique views on brain structure and function; i.e., how the brain is wired, and where and when activity takes place. Data acquired using these techniques can be analyzed in terms of its network structure to reveal organizing principles at the systems level. Graph representations are versatile models where nodes are associated to brain regions and edges to structural or functional connections. Structural graphs model neural pathways in white matter, which are the anatomical backbone between regions. Functional graphs are built based on functional connectivity, which is a pairwise measure of statistical interdependency between pairs of regional activity traces. Therefore, most research to date has focused on analyzing these graphs reflecting structure or function. Graph signal processing (GSP) is an emerging area of research where signals recorded at the nodes of the graph are studied atop the underlying graph structure. An increasing number of fundamental operations have been generalized to the graph setting, allowing to analyze the signals from a new viewpoint. Here, we review GSP for brain imaging data and discuss their potential to integrate brain structure, contained in the graph itself, with brain function, residing in the graph signals. We review how brain activity can be meaningfully filtered based on concepts of spectral modes derived from brain structure. We also derive other operations such as surrogate data generation or decompositions informed by cognitive systems. In sum, GSP offers a novel framework for the analysis of brain imaging data.

In this paper, we study the problem of jointly routing and scheduling traffic in an energy harvesting network. To this end, we leverage stochastic dual descent methods to propose a generalization of the well-known backpressure algorithm to energy harvesting networks. We name this policy energy harvesting backpressure (EH-BP) and show that it satisfies the fundamental property of backpressure-type algorithms. Namely, if given data arrival rates can be supported by given energy arrival rates and some routing-scheduling policy, they can be supported by the EH-BP policy. Numerical results attest to the properties of the proposed policy.

Sampling is a fundamental topic in graph signal processing with applications in estimation, clustering, and video compression. In contrast to traditional signal processing, however, the irregularity of the signal domain makes the selection of the sampling points non-trivial and hard to analyze. Indeed, although graph signal reconstruction is well-understood in the noiseless case, performance bounds for the interpolation of noisy samples exist mainly for randomized sampling schemes. This paper addresses this issue by deriving a lower bound on the mean-square interpolation error for graph signals. This bound is universal in the sense that it is not restricted to a specific sampling method and holds for all sampling sets. Simulations illustrate the tightness of the bound, which is then used to evaluate the performance of greedy sampling. Finally, a solution to the complexity issues of kernel principal component analysis is proposed using graph signal sampling.

The ability to obtain accurate estimators from a set of measurements is a key factor in science and engineering. Typically, there is an inherent assumption that the measurements were taken in a sequential order, be it in space or time. However, data is increasingly irregular so this assumption of sequentially obtained measurements no longer holds. By leveraging notions of graph signal processing to account for these irregular domains, we propose an unbiased estimator for the mean of a wide sense stationary graph process based on the diffusion of a single realization. We also provide a bound on the estimation error and determine the conditions for a specific rate of convergence of the estimator to the mean, in a weak law of large numbers fashion.

This paper presents methods to analyze functional brain networks and signals from graph spectral perspectives. The notion of frequency and filters recently generalized to irregular graph domains defines brain graph frequencies associated with different levels of spatial smoothness across the brain regions. Brain network frequency also enables the decomposition of brain signals into pieces corresponding to smooth or rapid variations. The methods are utilized to analyze brain networks and signals as subjects master a simple motor skill. We observe that brain signals corresponding to different graph frequencies exhibit different levels of contribution to active learning. Specifically, we notice a strong association between graph spectral properties of brain networks and the level of exposure to tasks performed, and recognize the most contributing and important frequency signatures at different task familiarity.

This paper examines metric spaces in which the distance between any pair of nodes is given by an interval. The goal is to investigate methods for hierarchical clustering, i.e., a family of nested partitions indexed by a connectivity parameter, deduced from the underlying distance intervals of the metric spaces. Our construction is based on designing admissible methods abiding to the axioms of value and transformation. Two admissible methods are constructed and are shown to provide upper and lower bounds in the space of all admissible methods. Practical implications are explored by clustering moving points via snapshots. The proposed clustering methods succeed in identifying underlying clustering structures via the maximum and minimum distances in all snapshots.

We consider stochastic nonparametric regression problems in a reproducing kernel Hilbert space (RKHS), an extension of expected risk minimization to nonlinear function estimation. Popular perception is that kernel methods are inapplicable to online settings, since the generalization of stochastic methods to kernelized function spaces require memory storage that is cubic in the iteration index (“the curse of kernelization”). We alleviate this intractability in two ways: (1) we consider the use of functional stochastic gradient method (FSGD) which operates on a subset of training examples at each step; and (2), we extract parsimonious approximations of the resulting stochastic sequence via a greedy sparse subspace projection scheme based on kernel orthogonal matching pursuit (KOMP). We establish that this method converges almost surely in both diminishing and constant algorithm step-size regimes for a specific selection of sparse approximation budget. The method is evaluated on a kernel multi-class support vector machine problem, where data samples are generated from class-dependent Gaussian mixture models.

We present an incremental Broyden-Fletcher-Goldfarb-Shanno (BFGS) method as a quasi-Newton algorithm with a cyclically iterative update scheme for solving large-scale optimization problems. The proposed incremental quasi-Newton (IQN) algorithm reduces computational cost relative to traditional quasi-Newton methods by restricting the update to a single function per iteration and relative to incremental second-order methods by removing the need to compute the inverse of the Hessian. A local superlinear convergence rate is established and a strong improvement is shown over first order methods numerically for a set of common large-scale optimization problems.

This paper considers the problem of minimizing the average of a finite set of strongly convex functions. We introduce a double incremental aggregated gradient method (DIAG) that computes the gradient of only one function at each iteration, which is chosen based on a cyclic scheme, and uses the aggregated average gradient of all the functions to approximate the full gradient. We prove that not only the proposed DIAG method converges linearly to the optimal solution, but also its linear convergence factor justifies the advantage of incremental methods on full batch gradient descent. In particular, we show theoretically and empirically that one pass of DIAG is more efficient than one iteration of gradient descent.

We consider supervised learning problems over training sets in which both the number of training examples and the dimension of the feature vectors are large. We focus on the case where the loss function defining the quality of the parameter we wish to estimate may be non-convex, but also has a convex regularization. We propose a Doubly Stochastic Successive Convex approximation scheme (DSSC) able to handle non-convex regularized expected risk minimization. The method operates by decomposing the decision variable into blocks and operating on random subsets of blocks at each step. The algorithm belongs to the family of successive convex approximation methods since we replace the original non-convex stochastic objective by a strongly convex sample surrogate function, and solve the resulting convex program, for each randomly selected block in parallel. The method operates on subsets of features (block coordinate methods) and training examples (stochastic approximation) at each step. In contrast to many stochastic convex methods whose almost sure behavior is not guaranteed in non-convex settings, DSSC attains almost sure convergence to a stationary solution of the problem. Numerical experiments on a non-convex variant of a lasso regression problem show that DSSC performs favorably in this setting.

Advancing a holistic theory of networks and network processes requires the extension of existing results in the processing of time-varying signals to signals supported on graphs. This paper focuses on the definition of stationarity and power spectral density for random graph signals, generalizes the concepts of autoregressive and moving average random processes to the graph domain, and investigates their parametric spectral estimation. Theoretical and algorithmic results are complemented with numerical tests on synthetic and real-world graphs.

We address the problem of identifying a graph structure from the observation of signals defined on its nodes. Fundamentally, the unknown graph encodes direct relationships between signal elements, which we aim to recover from observable indirect relationships generated by a diffusion process on the graph. We put forth a novel network topology inference approach whereby we: i) identify the eigenvectors of a matrix representation of the graph from realizations of the diffused signal; and ii) rely on these (possibly imperfect) spectral templates to estimate the eigenvalues by imposing desirable properties on the graph to be recovered. Robust algorithms with quantifiable performance are developed for the pragmatic settings where the eigenvectors are estimated with errors, or, when the eigenbasis is only partially known. Numerical tests showcase the effectiveness of the proposed algorithm in recovering amino-acid networks.

This work provides performance guarantees for the greedy solution of experimental design problems. In particular, it focuses on A- and E-optimal designs, for which typical guarantees do not apply since the mean-square error and the maximum eigenvalue of the estimation error covariance matrix are not supermodular. To do so, it leverages the concept of approximate supermodularity to derive non-asymptotic worst-case suboptimality bounds for these greedy solutions. These bounds reveal that as the SNR of the experiments decreases, these cost functions behave increasingly as supermodular functions. As such, greedy A- and E-optimal designs approach (1-1/e)-optimality. These results reconcile the empirical success of greedy experimental design with the non-supermodularity of the A- and E-optimality criteria.

This paper studies empirical risk minimization (ERM) problems for large-scale datasets and incorporates the idea of adaptive sample size methods to improve the guaranteed convergence bounds for first-order stochastic and deterministic methods. In contrast to traditional methods that attempt to solve the ERM problem corresponding to the full dataset directly, adaptive sample size schemes start with a small number of samples and solve the corresponding ERM problem to its statistical accuracy. The sample size is then grown geometrically -- e.g., scaling by a factor of two -- and use the solution of the previous ERM as a warm start for the new ERM. Theoretical analyses show that the use of adaptive sample size methods reduces the overall computational cost of achieving the statistical accuracy of the whole dataset for a broad range of deterministic and stochastic first-order methods. The gains are specific to the choice of method. When particularized to, e.g., accelerated gradient descent and stochastic variance reduce gradient, the computational cost advantage is a logarithm of the number of training samples. Numerical experiments on various datasets confirm theoretical claims and showcase the gains of using the proposed adaptive sample size scheme.

We develop a hybrid system architecture that enables a team of mobile robots to complete a task in a complex environment by self-organizing into a multihop ad hoc network and solving the concurrent communication and mobility problem. The proposed system consists of a two-layer feedback loop. An outer loop performs infrequent global coordination and a local inner loop determines motion and communication variables. This system provides the lightweight coordination and responsiveness of decentralized systems while avoiding local minima. This allows a team to complete a task in complex environments while maintaining desired end-to-end data rates. The behavior of the system is evaluated in experiments that demonstrate: 1) successful task completion in complex environments; 2) achievement of equal or greater end-to-end data rates as compared to a centralized system; and 3) robustness to unexpected events such as motion restriction.

We present a novel method to hierarchically cluster networked data allowing nodes to simultaneously belong to multiple clusters. Given a network, our method outputs a cut metric on the underlying node set, which can be related to data coverings at different resolutions. The cut metric is obtained by averaging a set of ultrametrics, which are themselves the output of (non-overlapping) hierarchically clustering noisy versions of the original network of interest. The resulting algorithm is illustrated in synthetic networks and is used to classify handwritten digits from the MNIST database.

High order networks are weighted complete hypergraphs collecting relationships between elements of tuples. Valid metric distances between high order networks have been defined but they are difficult to compute when the number of nodes is large. We relate high order networks to the filtrations of simplicial complexes and show that the distance between networks can be lower bounded by the difference between the homological features of their respective filtrations. Practical implications are explored by comparing the coauthorship networks of engineering and mathematics academic journals. The lower bounds succeed in discriminating engineering communities from mathematics and in differentiating engineering communities with different research interests.

We consider stochastic optimization problems in multi-agent settings, where a network of agents aims to learn decision variables which are optimal in terms of a global objective, while giving preference to locally and sequentially observed information. To do so, we formulate a problem where each agent minimizes a global objective while enforcing network proximity constraints, which includes consensus optimization as a special case. We propose a stochastic variant of the saddle point algorithm proposed by Arrow and Hurwicz to solve it, which yields a decentralized algorithm that is shown to asymptotically converge to a primal-dual optimal pair of the problem in expectation when a diminishing algorithm step-size is chosen. Moreover, the algorithm converges linearly to a neighborhood when a constant step-size is chosen. We apply this method to the problem of sequentially estimating a correlated random field in a sensor network, which corroborates these performance guarantees.

This paper presents diffusion filtering as a method to smooth signals defined on the nodes of a graph or network. Diffusion filtering considers the given signals as initial temperature distributions in the nodes and diffuses heat through the edges of the graph. The filtered signal is determined by the accumulated temperatures over time at each node. We show multiple other interpretations of diffusion filtering and describe how it can be generalized to encompass a wide class of networks making it suitable for real-world applications. We prove that diffused signals are stable to perturbations in the underlying network. Further, we demonstrate how diffusion filtering can be applied to improve the performance of recommendation systems by considering the problem of predicting ratings from a signal processing perspective.

A novel scheme for sampling graph signals is proposed. Space-shift sampling can be understood as a hybrid scheme that combines selection sampling -- observing the signal values on a subset of nodes - and aggregation sampling - observing the signal values at a single node after successive aggregation of local data. Under the assumption of bandlimitedness, we state conditions and propose strategies for signal recovery in different settings. Being a more general procedure, space-shift sampling achieves smaller reconstruction errors than current schemes, as we illustrate through the reconstruction of the industrial activity in a graph of the U.S. economy.

Network processes are often represented as signals defined on the vertices of a graph. To untangle the latent structure of such signals, one can view them as outputs of linear graph filters modeling underlying network dynamics. This paper deals with the problem of joint identification of a graph filter and its input signal, thus broadening the scope of classical blind deconvolution of temporal and spatial signals to the less-structured graph domain. Given a graph signal y modeled as the output of a graph filter, the goal is to recover the vector of filter coefficients h, and the input signal x which is assumed to be sparse. While y is a bilinear function of x and h, the filtered graph signal is also a linear combination of the entries of the "lifted" rank-one, row-sparse matrix xhT. The blind graph filter identification problem can be thus tackled via rank and sparsity minimization subject to linear constraints, an approach amenable to convex relaxation. An algorithm for jointly processing multiple output signals corresponding to different sparse inputs is also developed. Numerical tests with synthetic and real-world networks illustrate the merits of the proposed algorithm, as well as the benefits of leveraging multiple signals to aid the blind identification task.

We introduce node-variant graph filters, which allow the simultaneous implementation of multiple (regular) graph filters at different nodes, and study their design to implement arbitrary linear transformations between graph signals. Node-variant graph filters can be implemented distributedly, making them suitable for networked settings. We determine spectral conditions under which a specific linear transformation can be implemented perfectly and, for the cases where perfect implementation is infeasible, the design of optimal approximations for different error metrics is analyzed. We demonstrate the practical relevance of the developed framework by studying the application of node-variant graph filters for analog network coding.

In this paper, we present a hybrid system architecture that enables a team of robots to self-organize into a multi-hop ad-hoc network allowing for the completion of a given task while providing the desired end-to-end data rates between designated robots. This architecture consists of a two stage feedback loop in which an outer loop provides infrequent global coordination and an inner loop, operating locally, controls the motion and network routing of each robot. The resulting system is able to operate dynamically in complex environments with minimal global coordination as demonstrated through multiple experiments. We conclude with a realistic application of our system, namely patrolling a set of hallways.

In this paper we propose a hybrid architecture that allows a team of mobile robots to self-organize into a multi-hop ad-hoc network and solve the joint mobility and communication problem in complex environments to complete a given task. The system consists of an outer global planning loop and an inner local loop responsible for motion and network routing, arranged in a two-stage feedback system. This system is able to leverage the benefits of previous systems, while avoiding their drawbacks. This results in a lightweight responsive system that is able to operate in complex environments with minimal global coordination while maintaining a minimum end-to-end data rate between robots. Two main benefits of our approach are demonstrated through experimentation superior performance over existing systems and dynamic adjustment to unexpected events. We conclude with a demonstration of the system operating in a realistic scenario, in which the team patrols a set of hallways.

In pursuit of increasing the operational tempo of a ground robotics platform in unknown domains, we consider the problem of predicting the distribution of structural state-estimation error due to poorly-modeled platform dynamics as well as environmental effects. Such predictions are a critical component of any modern control approach that utilizes uncertainty information to provide robustness in control design. We use an online learning algorithm based on matrix factorization techniques to fit a statistical model of error that provides enough expressive power to enable prediction directly from motion control signals and low-level visual features. Moreover, we empirically demonstrate that this technique compares favorably to predictors that do not incorporate this information.

We consider empirical risk minimization for large-scale datasets. We introduce Ada Newton as an adaptive algorithm that uses Newton's method with adaptive sample sizes. The main idea of Ada Newton is to increase the size of the training set by a factor larger than one in a way that the minimization variable for the current training set is in the local neighborhood of the optimal argument of the next training set. This allows to exploit the quadratic convergence property of Newton's method and reach the statistical accuracy of each training set with only one iteration of Newton's method. We show theoretically that we can iteratively increase the sample size while applying single Newton iterations without line search and staying within the statistical accuracy of the regularized empirical risk. In particular, we can double the size of the training set in each iteration when the number of samples is sufficiently large. Numerical experiments on various datasets confirm the possibility of increasing the sample size by factor 2 at each iteration which implies that Ada Newton achieves the statistical accuracy of the full training set with about two passes over the dataset.

This paper considers optimization problems where nodes of a network have access to summands of a global objective. Each of these local objectives is further assumed to be an average of a finite set of functions. The motivation for this setup is to solve large scale machine learning problems where elements of the training set are distributed to multiple computational elements. The decentralized double stochastic averaging gradient (DSA) algorithm is proposed as a solution alternative that relies on: (i) The use of local stochastic averaging gradients. (ii) Determination of descent steps as differences of consecutive stochastic averaging gradients. Strong convexity of local functions and Lipschitz continuity of local gradients is shown to guarantee linear convergence of the sequence generated by DSA in expectation. Local iterates are further shown to approach the optimal argument for almost all realizations. The expected linear convergence of DSA is in contrast to the sublinear rate characteristic of existing methods for decentralized stochastic optimization. Numerical experiments on a logistic regression problem illustrate reductions in convergence time and number of feature vectors processed until convergence relative to these other alternatives.

A game-theoretic framework based on smart pricing in power grids that incorporates heterogeneous user preferences and renewable power uncertainty is considered. The system operator adopts an adaptive pricing policy that depends on total consumption and renewable generation. The pricing policy sets up a non-cooperative game of incomplete information among users with heterogeneous preferences. Selfish, altruistic and welfare maximizing user behavior models are proposed. Information exchange models in which users only have private information, communicate or receive broadcasted information are considered. For each pair of behavior and information exchange models, rational consumption strategy is characterized. Numerical analyses reveal that communication is beneficial for the expected aggregate payoff while it does not affect the expected net revenue of the system operator. Moreover, the additional information to the users helps reduce the variance of total consumption among runs increasing the accuracy of demand predictions.

This paper presents two families of distances in the space of high order proximity networks. The distances measure differences between networks and are shown to be valid metrics in the space of high order proximity networks modulo permutation isomorphisms. Practical implications are explored by comparing the coauthorship networks of two popular signal processing researchers. The metrics succeed in identifying their respective collaboration patterns.

An algorithm to learn optimal actions in distributed convex repeated games is developed. Learning is repeated because cost functions are revealed sequentially and distributed because they are revealed to agents of a network that can exchange information with neighboring nodes only. Learning is measured in terms of the global networked regret, which is the accumulated loss of causal prediction with respect to a centralized clairvoyant agent to which the information of all times and agents is revealed at the initial time. We use a variant of the Arrow-Hurwicz saddle point algorithm which penalizes local agent disagreement via Lagrange multipliers and leads to a distributed online algorithm. We show that decisions made with this saddle point algorithm lead to regret whose order is not larger than O(√T), where T is the total number of rounds of the game. Numerical behavior is illustrated for the particular case of dynamic sensor network estimation across different network sizes, connectivities, and topologies.

Agents of a network have access to strongly convex local functions fiand attempt to minimize the aggregate function f(x) = Σi=1nfi(x) while relying on variable exchanges with neighboring nodes. Various methods to solve this distributed optimization problem exist but they all rely on first order information. This paper introduces Network Newton, a method that incorporates second order information via distributed evaluation of approximations to Newton steps. The method is shown to converge linearly and to do so while exhibiting a quadratic phase. Numerical analyses show substantial reductions in convergence times relative to existing (first order) alternatives.

This paper introduces a formal definition of continuity and generalizes an existing notion of stability for node centrality measures in weighted graphs. It is shown that the frequently used measures of degree, closeness and eigenvector centrality are stable and continuous whereas betweenness centrality is neither. Numerical experiments in synthetic and real-world networks show that both stability and continuity are desirable in practice since they imply different levels of robustness in the presence of noisy data. In particular, a stable alternative of betweenness centrality is shown to exhibit resilience against noise while preserving its notion of centrality.

We consider discriminative dictionary learning in a distributed online setting, where a team of networked robots aims to jointly learn both a common basis of the feature space and a classifier over this basis from sequentially observed signals. We formulate this problem as a distributed stochastic program with a non-convex objective and present a block variant of the Arrow-Hurwicz saddle point algorithm to solve it. Only neighboring nodes in the communications network need to exchange information, and we penalize the discrepency between the individual feature basis and classifiers using Lagrange multipliers. The application we consider is for a team of robots to collaboratively recognize objects of interest in dynamic environments. As a preliminary performance benchmark, we consider the problem of learning a texture classifier across a network of robots moving around an urban setting where separate training examples are sequentially observed at each robot. Results are shown for both a standard texture dataset and a new dataset from an urban training facility, and we compare the performance of the standard centralized construction to the new distributed algorithm for the case when distinct samples from all classes are seen by the robots. These experiments yield comparable performance between the decentralized and the centralized cases, demonstrating the proposed method's practical utility.

A Discounted Integral Priority (DIP) packet routing algorithm is presented. The method is derived for the network flow model of packet routing used for the derivation of backpressure type methods. Unlike backpressure type methods, DIP routing is designed to reduce the queue lengths rather than simply stabilize them. Our work leverages time discounted integral control to generate an adaptive packet routing algorithm which significantly outperforms its optimization motivated counterparts. Connections are drawn with stochastic heavy ball methods which allow implementation of a decaying stepsize. Stability proofs are presented for a stochastic heavy ball variant of the Discounted Integral Priority routing algorithm with a decaying step size. Our numerical experiments implement Discounted Integral Priority Routing with a unit step size and demonstrate fast convergence and significantly smaller steady state queue backlogs as compared with Soft Backpressure and Accelerated Backpressure.

We consider a demand side management model in which the power provider adopts an adaptive pricing strategy that depends on fluctuations in renewable sources and consumption behavior of customers with heterogeneous marginal utilities in the smart grid. Given the adaptive pricing strategy, we formulate the power consumption behavior of customers as a repeated noncooperative game with incomplete information. We provide an explicit characterization of unique Bayesian Nash equilibrium strategy in terms of individual marginal utilities. The rational behavior is also characterized in a communication scheme where smart meters exchange consumption levels with neighboring meters. A local algorithm that computes equilibrium consumption and propagates beliefs is presented when the network is known. Simulation results show that communication is beneficial for welfare and that power provider can lower the peak-to-average ratio of total consumption by adjusting its target profit ratio.

We consider a repeated game in which a team of agents share a common, but only partially known, task. The team also has the goal to coordinate while completing the task. This creates a trade-off between estimating the task and coordinating with others reminiscent of the kind of trade-off exemplified by the Keynesian beauty contest game. The agents thus can benefit from learning from others. This paper provides a survey of results from [1-4]. We first present a recent result that states repeated play of the game by myopic but Bayesian agents, who observe the actions of their neighbors over a connected network, eventually yield coordination on a single action. Furthermore, the coordinated action is equal to the mean estimate of the common task given individual's information. This indicates that agents in the network have the same mean estimate in the limit despite the differences in the quality of local information. Finally, we state that if the space of signals is a finite set, the coordinated action is equal to the estimate of the common task given full information, that is, agents eventually aggregate the information available throughout the network on the common task optimally.

This paper considers an online convex optimization problem in a distributed setting, where a connected network collectively solves a learning problem while only exchanging information between neighboring nodes. We formulate two expressions to describe distributed regret and present a variant of the Arrow-Hurwicz saddle point algorithm to solve the distributed regret minimization problem. Using Lagrange multipliers to penalize the discrepancy between them, only neighboring nodes exchange decision values and Lagrange multipliers. We show that decisions made with this saddle point algorithm lead to vanishing regret of the order of O(1/√T) where T is the final iteration time, and further depends on the smoothness of the cost functions and the size and connectivity of the network. Using a recursive least squares example, we find that the numerical results corroborate our theoretical findings.

This paper develops a decentralized linearized alternating direction method of multipliers (LADMM) that minimizes the sum of local cost functions in a multi-agent network. Through linearizing the local cost functions agents can obtain their local solutions with simple algebraic operations and gradient descent steps. We prove that the algorithm linearly converges to the optimal solution given that the local cost functions are strongly convex and have Lipschitz gradients. The decentralized LADMM has similar computations as the distributed (sub)gradient method but outperforms the latter, which is unable to achieve linear rate of convergence and convergence to the exact optimal solution simultaneously. Compared to its non-linearized counterpart that suffers from high computation burden, the decentralized LADMM has a comparable rate of convergence according to both theoretical analysis and numerical experiments.

This paper adapts a recently developed regularized stochastic version of the Broyden, Fletcher, Goldfarb, and Shanno (BFGS) quasi-Newton method for the solution of support vector machine classification problems. The proposed method is shown to converge almost surely to the optimal classifier at a rate that is linear in expectation. Numerical results show that the proposed method exhibits a convergence rate that degrades smoothly with the dimensionality of the feature vectors.

This paper presents a formal definition of stability for node centrality measures in networks and shows that the well-known betweenness centrality is not stable with respect to that metric. An alternative definition that preserves the same centrality notion while satisfying this stability criterion is then introduced. The practical implications of stability are explored by studying the behavior of the traditional as well as the alternative stable betweenness centrality in both, synthetic random networks, and the network of interactions between sectors of the United States economy.

This paper introduces hierarchical quasi-clustering methods, a generalization of hierarchical clustering for asymmetric networks where the output structure preserves the asymmetry of the input data. We show that this output structure is equivalent to a finite quasi-ultrametric space and study admissibility with respect to two desirable properties. We prove that a modified version of single linkage is the only admissible quasi-clustering method. Moreover, we show stability of the proposed method and we establish invariance properties fulfilled by it. Algorithms are further developed and the value of quasi-clustering analysis is illustrated with a study of internal migration within United States.

Providing reliable end-to-end communication for teams of robots requires the integration of novel routing techniques, motion planning algorithms, and transport level communication protocols. In this paper we look at existing robust routing solutions that provide redundancy at the routing layer and develop the Multi-Confirmation Transmission Protocol (MCTP) to take advantage of that redundancy at the transport level. The resulting system that integrates robust routing and MCTP is evaluated in experiments performed in complex environments. The integrated system is observed to provide a robust architecture that allows for near lossless communication while operating in a complex environment with less traffic than standard confirmation protocols.

We develop an Accelerated Back Pressure (ABP) algorithm using Accelerated Dual Descent (ADD), a distributed approximate Newton-like algorithm that only uses local information. Our construction is based on writing the backpressure algorithm as the solution to a network feasibility problem solved via stochastic dual subgradient descent. We apply stochastic ADD in place of the stochastic gradient descent algorithm. We prove that the ABP algorithm guarantees stable queues. Our numerical experiments demonstrate a significant improvement in convergence rate, especially when the packet arrival statistics vary over time.

We present an axiomatic construction of hierarchical clustering in asymmetric networks where the dissimilarity from node a to node b is not necessarily equal to the dissimilarity from node b to node a. The theory is built on the axioms of value and transformation which encode desirable properties common to any clustering method. Two hierarchical clustering methods that abide to these axioms are derived: reciprocal and nonreciprocal clustering. We further show that any clustering method that satisfies the axioms of value and transformation lies between reciprocal and nonreciprocal clustering in a well defined sense. We apply this theory to the formation of circles of trust in social networks.

A repeated network game where agents' utilities depend on information and payoff externalities is considered. Agents play Bayesian Nash Equilibrium strategies with respect to their beliefs on the state of the world and the actions of all other nodes in the network. These beliefs are refined over subsequent stages based on the observed actions of neighboring peers. This paper introduces the Quadratic Network Game (QNG) filter that agents can run locally to update their beliefs, select corresponding optimal actions, and eventually learn a sufficient statistic of the network's state. The QNG filter is demonstrated on a coordination game.

We present an authorship attribution method based on relational data between function words. These are content independent words that help define grammatical relationships. As relational structures we use normalized word adjacency networks. We interpret these networks as Markov chains and compare them using entropy measures. We illustrate the accuracy of the method developed through a series of numerical experiments including comparisons with frequency based methods. We show that accuracy increases when combining relational and frequency based data, indicating that both sources of information encode different aspects of authorial styles.

A network of social agents wants to minimize a global cost given by a sum of local terms involving convex nonlinear functions of self and neighboring variables. Agents update their variables at random times according to a random heuristic rule that is on average optimal with respect to the local cost given values of neighboring agents. When all agents apply heuristic rational optimization, convergence result shows that global cost visits a neighborhood of optimal cost infinitely often with probability 1. An exponential probability bound on the worst deviation from optimality between visits to near optimal operating points is also presented. Models of opinion propagation and voting are cast in the language of heuristic rational optimization. Numerical results are presented for the opinion propagation model on both geometric and small-world network structures.

This paper considers algorithms for optimal transmission over wireless multiuser channels where the transmitter has access to imperfect channel state information (CSI). We focus on downlink orthogonal frequency division multiple access and multiuser uplink random access. In both cases, frequency assignment, transmitted power, and coding mode are adapted to imperfect CSI in order to maximize expected transmission rate subject to average power constraints. Determination of optimal solutions is a non-convex stochastic optimization problem with infinitely many variables. Exploiting its property of null duality gap, we show that optimal solutions are determined by optimal dual variables. This affords considerable simplification because the dual optimization problem is convex and finite-dimensional. Iterative algorithms that find the optimal operating point based on imperfect CSI without having access to the channels' probability distributions are further developed.

This paper develops a framework for the estimation of a time-varying random signal using a wireless sensor network. Given a continuous time model, sensors collect noisy observations and produce local estimates according to the discrete-time equivalent system defined by the sampling period of observations. Estimation is performed using a maximum a posteriori probability estimator (MAP) within a given window of interest. To mediate the incorporation of information from other sensors we introduce Lagrange multipliers to penalize the disagreement between neighboring estimates. We show that the resulting distributed (D-)MAP algorithm is able to track dynamical signals with a small error. This error is characterized in terms of problem constants and vanishes with the sampling time as long as the log-likelihood function satisfies a smoothness condition.

Wireless mesh networks hold the promise of rapid and flexible deployments of communication facilities. This potential notwithstanding, the often erratic behavior of multihop wireless transmissions is limiting the range of applications that such networks can target. In this paper we investigate the feasibility and benefits of a routing protocol explicitly aimed at making wireless mesh networks more predictable while preserving their efficiency and flexibility. The protocol's basic premise is the classical idea that a multipath solution can offer resiliency to unexpected link variations. The paper's contributions are in demonstrating how this can be effectively realized in a wireless context, and in offering initial evidences of its efficacy. In particular, the paper illustrates how routing decisions that account for link variability can be computed in a distributed fashion, and the benefits they afford in improving the stability of end-to-end transmission rates even in the presence of random network fluctuations.

We propose an architecture and algorithms for maintaining end-to-end network connectivity for autonomous teams of robots. By adopting stochastic models of point-to-point wireless communication and computing robust solutions to the network routing problem, we ensure reliable connectivity during robot movement in complex environments. We fully integrate the solution to network routing with the choice of node positions through the use of randomized motion planning techniques. Experiments demonstrate that our method succeeds in navigating a complex environment while ensuring that end-to-end communication rates meet or exceed prescribed values within a target failure tolerance.

Cooperation between multiple autonomous vehicles requires inter-vehicle communication, which in many scenarios must be established over an ad-hoc wireless network. This paper proposes an optimization-based approach to the deployment of such mobile robotic networks. A primal-dual gradient descent algorithm jointly optimizes the steady-state positions of the robots based on the specification of a high-level task in the form of a potential field, and routes packets through the network to support the communication rates desired for the application. The motion planning and communication objectives are tightly coupled since the link capacities depend heavily on the relative distances between vehicles. The algorithm decomposes naturally into two components, one for position optimization and one for communication optimization, coupled via a set of Lagrange multipliers. Crucially and in contrast to previous work, our method can rely on on-line evaluation of the channel capacities during deployment instead of a prespecified model. In this case, a randomized sampling scheme along the trajectories allows the robots to implement the algorithm with minimal coordination overhead.

In this paper, a system architecture to provide end-to-end network connectivity for autonomous teams of robots is discussed. The core of the proposed system is a cyber-physical controller whose goal is to ensure network connectivity as robots move to accomplish their assigned tasks. Due to channel quality uncertainties inherent to wireless propagation, we adopt a stochastic model where achievable rates are modeled as random variables. The cyber component of the controller determines routing variables that maximize the probability of having a connected network for given positions. The physical component determines feasible robot trajectories that are restricted to safe configurations which ensure these probabilities stay above a minimum reliability level. Local trajectory planning algorithms are proposed for simple environments and leveraged to obtain global planning algorithms to handle complex surroundings. The resulting integrated controllers are robust in that end-to-end communication survives with high probability even if individual point-to-point links are likely to fail with significant probability. Experiments demonstrate that the global planning algorithm succeeds in navigating a complex environment while ensuring that end-to-end communication rates meet or exceed prescribed values within a target failure tolerance.

This paper considers a wireless channel when the probability distribution of fading is unknown and the transmitter has access to imperfect channel state information (CSI). Transmitted power and coding mode are adapted to the available imperfect CSI through the use of a backoff function in order to maximize the expected transmission rate subject to an average power constraint. Determination of the optimal power allocation and backoff function is a non-convex stochastic optimization problem with infinitely many variables. Despite its non-convexity, the duality gap of this problem has been shown to be null. Exploiting this property, we show that the optimal power allocation and channel backoff functions are uniquely determined by the optimal dual variable. This affords considerable simplification because the dual optimization problem is convex and one-dimensional -- whereas the original primal problem is non-convex and infinite-dimensional. Iterative algorithms that find the optimal power and backoff function based on imperfect CSI without having access to the channel probability distribution are further developed. Numerical results are provided to corroborate theoretical findings.

We consider distributed algorithms to optimize random access multihop wireless networks in the presence of fading. Since the associated optimization problem is neither convex nor amenable to distributed implementation, we introduce a problem approximation. This approximation is still not convex, but it has zero duality gap and can be solved and decomposed into local subproblems in the dual domain. The solution method is through a stochastic subgradient descent algorithm that operates without knowledge of the fading's distribution and leads to an architecture composed of layers and layer interfaces. With limited amount of message passing among terminals and small computational cost, the proposed algorithm converges almost surely in an ergodic sense.

We develop adaptive scheduling and power control algorithms for random access in a multiple access channel where terminals acquire instantaneous channel state information but do not know the probability distribution of the channel. In each time slot, terminals measure the channel to the common access point. Based on the observed channel value, they determine whether to transmit or not and, if they decide to do so, adjust their transmitted power. We remark that there is no coordination between terminals and that adaptation is to the local channel value only. It is shown that the proposed algorithm almost surely maximizes a proportional fair utility while adhering to instantaneous and average power constraints. Important properties of the algorithm are low computational complexity and the ability to handle non-convex rate functions. Numerical results on a randomly generated network with heterogeneous users corroborate theoretical results.

This paper introduces ergodic stochastic optimization (ESO) algorithms to solve resource allocation problems that involve a random state and where optimality criteria are expressed in terms of long term averages. A policy that observes the state and decides on a resource allocation is proposed and shown to almost surely satisfy problem constraints and optimality criteria. Salient features of the ESO algorithm are that it does not require access to the state's probability distribution, that it can handle non-convex constraints in the resource allocation variables, and that convergence to optimal operating points holds almost surely. ESO is applied to determine operating points of an orthogonal frequency division multiplexing broadcast channel that maximize a given rate utility.

A general wireless networking problem is formulated whereby end-to-end user rates, routes, link capacities, transmit-power, frequency, and power resources are jointly optimized across fading states. Even though the resultant optimization problem is generally nonconvex, it is proved that the gap with its Lagrange dual problem is zero, so long as the underlying fading distribution function is continuous. The major implication is that separating the design of wireless networks in layers and per-fading state subproblems can be optimal. Subgradient descent algorithms are further developed to effect an optimal separation in layers and layer interfaces.

Optimal and reduced-complexity near-optimal algorithms are developed for the design of wireless networks in the presence of fading. The physical layer is interference-limited, whereby network terminals treat interference as noise. Optimal wireless network design amounts to joint optimization of application-level rates, routes, link capacities, power consumption, and power allocation across frequency tones, neighboring terminals, and fading states. The present contribution shows how recent results establishing the optimality of layered architectures can be realized in practice by developing physical layer resource allocation algorithms that are seamlessly integrated into layered architectures without loss of optimality. Specifically, the provably convergent algorithms yield (near-)optimal end-to-end rates, multicommodity flows, link capacities, and average powers. These design variables are obtained offline, and are subsequently used for control during network operation.

This paper develops near-optimal designs of wireless networks in the presence of fading. The novel approach optimizes jointly application level rates, routes, link capacities, power consumption and physical layer parameters. The physical layer is interference limited with terminals distributing their power budget among frequency tones, neighboring nodes and fading states. The present contribution builds on recent results establishing the optimality of layered architectures and develops physical layer resource allocation algorithms that are seamlessly integrated into layered architectures without loss of optimality.

This paper proposes an optimal architecture for wireless networks based on layers and layer interfaces. In the presence of fading the architecture is shown to be optimal. The result follows from a subgradient descent algorithm on the dual function of a generic wireless networking optimization problem. The fact that these non-convex optimization problems have nonetheless zero duality gap is exploited.

We consider state estimation of a Markov stochastic process using an ad hoc wireless sensor network (WSN) based on noisy linear observations. Due to power and bandwidth constraints present in resource- limited WSNs, the observations are quantized before transmission. We derive a distributed recursive mean-square error (MSE) optimal quantizer-estimator based on the quantized observations. The resultant Kalman-like algorithm based on quantized observations exhibits MSE performance and computational complexity comparable to the Kalman filter based on un-quantized observations even for 2-3 bits of quantization per observation.

We formulate a frequency-division multiple access (FDMA) networking problem for wireless mobile ad-hoc networks (MANETS) to jointly optimize end-to-end user rates, routes, link capacities, transmitted power, frequency and power allocation across subcarriers and fading states. We show that the resulting non-convex optimization problem has zero duality gap. For some types of FDMA networks this result is exploited to reformulate the original problem into a (computationally tractable) convex optimization problem. We further exploit the lack of duality gap to show that conventional layering can be optimal in FDMA wireless MANETS. Specifically, if we select Lagrange multipliers appropriately, we can decompose the original problem in smaller sub-problems associated with the conventional networking layers. The solution of these per-layer optimization problems coincides with the solution of the originally formulated cross-layer optimization problem.

A novel framework was introduced recently for stochastic routing in wireless multihop networks, whereby each node selects a neighbor to forward a packet according to a probability distribution. Generalizing (deterministic) shortest path routing, stochastic routing offers greater flexibility that matches the random nature of wireless links. Consider the pairwise reliability matrix R, whose (i, j)-th entry Rijrepresents the probability that a packet transmitted from the j-th user Ujis correctly received by the i-th user Ui. Using R to capture physical layer aspects of the wireless medium, several rate-oriented stochastic routing formulations can be reduced to centrally solvable convex optimization problems. The present paper, introduces distributed algorithms that find optimal routing probabilities without the burden of collecting R at a central node and then percolating the resulting routing probabilities through network nodes. The resultant schemes are distributed in the sense that: (i) terminal Ujhas access only to the j-th row and column of R; and (ii) Ujinterchanges variables only with those single-hop neighbors having positive probability of decoding its packets. The distributed algorithms are built by recasting the optimization problems and applying dual decomposition techniques. Since iterates obtained via dual decomposition do not always converge to centralized optimal routing probabilities, two known regularization approaches are further invoked, namely the method of multipliers (MoM) and the alternating-direction MoM. Convergence to the optimal routing matrix is then guaranteed under mild conditions. Many rate-oriented optimality criteria of practical interest can be addressed by the distributed framework, including maximization of: (i) the minimum rate; (ii) a weighted sum of rates; (iii) the product of rates; and (iv) the source's rate in a relay network. Robustness of the distributed algorithms is tested with respect to "topological" changes, communication errors and node mobility.

We introduce distributed algorithms to find rate-optimal routes based on local knowledge of the pairwise error probability (reliability) matrix. The distributed algorithms are built by (re)-formulating optimization problems amenable to application of dual decomposition techniques. Convergence of our algorithms to the optimal routing matrix is guaranteed under mild conditions. Many rate-optimality criteria of practical interest can be casted in our framework including maximization of: i)worst user's rate; ii) weighted sum of rates; iii) product of rates; and iv) relay network rate. We test robustness of our algorithms to node mobility.

We deal with distributed estimation of deterministic vector parameters using ad hoc wireless sensor networks (WSNs). We cast the decentralized estimation problem as the solution of multiple convex optimization subproblems. Using the method of alternating multipliers we derive algorithms which are decomposable into a set of simpler tasks suitable for distributed implementation. Different from existing alternatives, our approach does not require knowing the desired estimator in closed-form thus allowing for distributed nonlinear estimation. Our algorithms have guaranteed convergence under ideal channel links, while they exhibit noise resilience provably established for the distributed best linear unbiased estimator (BLUE).

We introduce a novel approach to multi-hop routing in wireless networks. Instead of the usual graph description we characterize the network by the packet delivery ratio matrix whose entries represent the probability that a given node decodes the packet transmitted by any other node. The model lends itself naturally to the formulation of stochastic routing protocols in which packets are randomly routed to neighboring nodes; and routing algorithms search for a matrix of routing probabilities according to properly defined optimality criteria. The goal of the paper is to show that this novel framework offers a useful model to aid in the design of optimal routing algorithms. In particular, it is established that: (i) performance is improved with respect to graph descriptions; and (ii) optimal routes can be obtained as the solution of optimization problems, many of which turn out to be convex and can thus be solved in polynomial time using interior point methods.

A general framework is developed for multi-source cooperation (MSC) protocols to improve diversity and spectral efficiency relative to repetition based alternatives that rely on single-source cooperation. The novel protocols are flexible to balance tradeoffs among diversity, spectral efficiency and decoding-complexity. Users are grouped in clusters and follow a two-phase MSC protocol which involves time division multiple access (TDMA) to separate users within a cluster, and code division multiple access (CDMA) used to separate clusters. An attractive protocol under the general MSC framework relies on distributed complex field coding (DCFC) to enable diversity order equal to the number of users per cluster. Cluster separation based on orthonormal spreading sequences leads to spectral efficiency 1/2. When the number of clusters exceeds the amount of spreading, spectral efficiency can be enhanced without sacrificing diversity, at the expense of controllable increase in complexity. Simulations corroborate our analytical claims

Well appreciated at the physical layer, user cooperation is introduced here as a diversity enabler for wireless random access (RA) at the medium access control sublayer. This is accomplished through a two-phase protocol in which active users start with a low power transmission attempting to reach nearby users and follow up with a high power transmission in cooperation with the users recruited in the first phase. We show that such a cooperative protocol yields a significant increase in throughput. Specifically, we prove that for networks with a large number of users, the throughput of a cooperative wireless RA network operating over Rayleigh-fading links approaches the throughput of an RA network operating over additive white Gaussian noise links—thus justifying the title of the paper. The message borne out of this result is that user cooperation offers a viable choice for migrating diversity benefits to the wireless RA regime, thus bridging the gap to wireline RA networks, without incurring a bandwidth or energy penalty.

Combining multi-source cooperation and link- adaptive regenerative techniques, we develop a novel protocol capable of achieving diversity up to the number of cooperating users and larger coding gains without incurring the overhead of cyclic redundancy check (CRC) codes. The resulting protocol can be further optimized to take advantage of the information provided by CRC when available. Simulations confirm our theoretical assessments.

We derive and analyze distributed state estimators of dynamical stochastic processes, whereby low communication cost is effected by requiring the transmission of a single bit per observation. Following a Kalman filtering (KF) approach, we develop recursive algorithms for distributed state estimation based on the sign of innovations (SOI). Even though SOI-KF can afford minimal communication overhead, we prove that in terms of performance and complexity it comes very close to the clairvoyant KF which is based on the analog-amplitude observations. Reinforcing our conclusions, we show that the SOI-KF applied to distributed target tracking based on distance only observations yields accurate estimates at low communication cost

Within a new paradigm, where wireless user cooperation is viewed as a form of (opportunistic) multipath, we exploit the unique capabilities of direct-sequence spread spectrum transmissions in handling multipath to design a novel spectrally efficient protocol for wireless cooperative networks. We show how and why our proposed system achieves diversity without increasing bandwidth. After analyzing its performance, we deduce that user capacity can be significantly improved with respect to existing third generation cellular systems in the uplink.

Wireless sensor networks deployed to perform surveillance and monitoring tasks have to operate under stringent energy and bandwidth limitations. These motivate well distributed estimation scenarios where sensors quantize and transmit only one, or a few bits per observation, for use in forming parameter estimators of interest. In a companion paper, we developed algorithms and studied interesting tradeoffs that emerge even in the simplest distributed setup of estimating a scalar location parameter in the presence of zero-mean additive white Gaussian noise of known variance. Herein, we derive distributed estimators based on binary observations along with their error-variance performance for unknown noise pdfs.

Cooperative wireless communication systems have attracted much attention in recent years, due to the diversity advantage they can afford. Existing cooperative transmission modalities have been developed in conjunction with fixed-rate multiplexing based on TDMA, CDMA or FDMA. We advocate user cooperation as the method of choice for enabling diversity in wireless random access networks. The specific protocol developed herein exploits the fact that user cooperation can be viewed as a form of multipath, and capitalizes on the suitability of long pseudo-noise (PN) spreading codes for dealing with multipath channels. Analysis and numerical results confirm that throughput increases considerably when random access via spread-spectrum slotted Aloha protocols is aided by user collaboration.

Wireless sensor networks deployed to perform surveillance and monitoring tasks have to operate under stringent energy and bandwidth limitations. These motivate well distributed estimation scenarios where sensors quantize and transmit only one, or a few bits per observation, for use in forming parameter estimators of interest. In a companion paper, we developed algorithms and studied interesting tradeoffs that emerge even in the simplest distributed setup of estimating a scalar location parameter in the presence of zero-mean additive white Gaussian noise of known variance. Herein, we derive distributed estimators based on binary observations along with their fundamental error-variance limits for more pragmatic signal models: i) known univariate but generally non-Gaussian noise probability density functions (pdfs); ii) known noise pdfs with a finite number of unknown parameters; and iii) practical generalizations to multivariate and possibly correlated pdfs. Estimators utilizing either independent or colored binary observations are developed and analyzed. Corroborating simulations present comparisons with the clairvoyant sample-mean estimator based on unquantized sensor observations, and include a motivating application entailing distributed parameter estimation where a WSN is used for habitat monitoring.

Random access Aloha protocols have well documented merits in terms of simplicity and favorable delay-throughput trade-off under moderate bursty traffic loads. Short spreading codes have been used in conjunction with random access to endow Aloha with benefits originating from spread-spectrum communications. Instead of short, symbol-periodic spreading, this paper considers long pseudo-random (PN) packet-periodic sequences in the context of spread-Aloha and establishes that long PN codes increase the maximum stable throughput by reducing the probability of collisions. Relying on a dominant system approach, we analyze the resultant throughput and demonstrate that increasing the PN code length quickly transforms the collision-limited channel to an interference-limited one. In particular, we investigate how throughput depends on user load and packet length. Finally, we discuss synchronization issues and provide corroborating numerical results.

Cooperative diversity (CD) networks have been receiving a lot of attention recently as a distributed means of improving error performance and capacity. For sufficiently large signal-to-noise ratio (SNR), this paper derives the average symbol error probability (SEP) for analog forwarding CD links. The resulting expressions are general as they hold for an arbitrary number of cooperating branches, arbitrary number of cooperating hops per branch, and various channel fading models. Their simplicity provides valuable insights to the performance of CD networks and suggests means of optimizing them. Besides revealing the diversity, they clearly show from where this advantage comes from and prove that presence of diversity does not depend on the specific (e.g., Rayleigh) fading distribution. Finally, they explain how diversity is improved in multihop CD networks.

Within a new paradigm, where wireless user cooperation is viewed as a form of (opportunistic) multipath, we exploit the unique capabilities of direct-sequence spread spectrum transmissions in handling multipath to design a novel spectrally efficient protocol for wireless cooperative networks. We show how and why our proposed system achieves diversity without increasing bandwidth. After analyzing its performance, we deduce that user capacity can be significantly improved with respect to existing third generation cellular systems in the uplink. This is particularly interesting since our scheme can be readily integrated in such networks without major changes in the existing standards.

Cooperative diversity (CD) networks have been receiving a lot of attention recently as a distributed means of improving error performance and capacity. This paper derives the average symbol error probability (SEP) for amplify and forward CD links. The resulting expressions are general as they hold for an arbitrary number of cooperating branches, arbitrary number of cooperating hops per branch, and many channel fading models. Their simplicity provides valuable insights to the performance of CD networks and allows their optimization. Besides revealing the diversity advantage, they clearly show from where this advantage comes from and prove that the diversity advantage holds independently of the channel fading model. Finally, explain how diversity is improved in multihop CD networks.