Catalog footprint

What is connected

97works
22topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

97 published item(s)

preprint2026arXiv

Consistent Geometric Deep Learning via Hilbert Bundles and Cellular Sheaves

Modern deep learning architectures increasingly contend with sophisticated signals that are natively infinite-dimensional, such as time series, probability distributions, or operators, and are defined over irregular domains. Yet, a unified learning theory for these settings has been lacking. To start addressing this gap, we introduce a novel convolutional learning framework for possibly infinite-dimensional signals supported on a manifold. Namely, we use the connection Laplacian associated with a Hilbert bundle as a convolutional operator, and we derive filters and neural networks, dubbed as \textit{HilbNets}. We make HilbNets and, more generally, the convolution operation, implementable via a two-stage sampling procedure. First, we show that sampling the manifold induces a Hilbert Cellular Sheaf, a generalized graph structure with Hilbert feature spaces and edge-wise coupling rules, and we prove that its sheaf Laplacian converges in probability to the underlying connection Laplacian as the sampling density increases. Notably, this result is a generalization to the infinite-dimensional bundle setting of the Belkin \& Niyogi \cite{BELKIN20081289} convergence result for the graph Laplacian to the manifold Laplacian, a theoretical cornerstone of geometric learning methods. Second, we discretize the signals and prove that the discretized (implementable) HilbNets converge to the underlying continuous architectures and are transferable across different samplings of the same bundle, providing consistency for learning. Finally, we validate our framework on synthetic and real-world tasks. Overall, our results broaden the scope of geometric learning as a whole by lifting classical Laplacian-based frameworks to settings where the signal at each point lives in its own Hilbert space.

preprint2026arXiv

Transferable Graphical MARL for Real-Time Estimation in Dynamic Wireless Networks

We study real-time sampling and estimation of autoregressive Markovian sources in decentralized and dynamic multi-hop networks that share similar structures. Nodes cache neighboring samples and communicate over wireless collision channels. The objective is to minimize the time-average estimation error and/or the age of information under decentralized policies, which we address by developing a unified graphical multi-agent reinforcement learning framework. A key feature of the framework is its transferability, enabled by the fact that the number of trainable parameters is independent of the number of agents, allowing a learned policy to be directly deployed on dynamic yet structurally similar graphs without re-training. Building on this design, we establish rigorous theoretical guarantees on the transferability of the resulting policies. Numerical experiments demonstrate that (i) our method outperforms state-of-the-art baselines on dynamic graphs; (ii) the trained policies transfer well to larger networks, with performance gains increasing with the number of nodes; and (iii) incorporating recurrence is crucial, enhancing resilience to non-stationarity in both independent learning and centralized training with decentralized execution.

preprint2023arXiv

coVariance Neural Networks

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.

preprint2023arXiv

Resilient Constrained Reinforcement Learning

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.

preprint2022arXiv

Graph Neural Networks for Decentralized Multi-Robot Submodular Action Selection

The problem of decentralized multi-robot target tracking asks for jointly selecting actions, e.g., motion primitives, for the robots to maximize target tracking performance with local communications. One major challenge for practical implementations is to make target tracking approaches scalable for large-scale problem instances. In this work, we propose a general-purpose learning architecture toward collaborative target tracking at scale, with decentralized communications. Particularly, our learning architecture leverages a graph neural network (GNN) to capture local interactions of the robots and learns decentralized decision-making for the robots. We train the learning model by imitating an expert solution and implement the resulting model for decentralized action selection involving local observations and communications only. We demonstrate the performance of our GNN-based learning approach in a scenario of active target tracking with large networks of robots. The simulation results show our approach nearly matches the tracking performance of the expert algorithm, and yet runs several orders faster with up to 100 robots. Moreover, it slightly outperforms a decentralized greedy algorithm but runs faster (especially with more than 20 robots). The results also exhibit our approach's generalization capability in previously unseen scenarios, e.g., larger environments and larger networks of robots.

preprint2022arXiv

Large-Scale Graph Reinforcement Learning in Wireless Control Systems

Modern control systems routinely employ wireless networks to exchange information between spatially distributed plants, actuators and sensors. With wireless networks defined by random, rapidly changing transmission conditions that challenge assumptions commonly held in the design of control systems, proper allocation of communication resources is essential to achieve reliable operation. Designing resource allocation policies, however, is challenging, motivating recent works to successfully exploit deep learning and deep reinforcement learning techniques to design resource allocation and scheduling policies for wireless control systems (WCSs). As the number of learnable parameters in a neural network grows with the size of the input signal, deep reinforcement learning may fail to scale, limiting the immediate generalization of such scheduling and resource allocation policies to large-scale systems. The interference and fading patterns among plants and controllers in the network, however, induce a time-varying graph that can be used to construct policy representations based on graph neural networks (GNNs), with the number of learnable parameters now independent of the number of plants in the network. We further establish in the context of WCSs that, due to inherent invariance to graph permutations, the GNN is able to model scalable and transferable resource allocation policies, which are subsequently trained with primal-dual reinforcement learning. Numerical experiments show that the proposed graph reinforcement learning approach yields policies that not only outperform baseline solutions and deep reinforcement learning based policies in large-scale systems, but that can also be transferred across networks of varying size.

preprint2022arXiv

Learning by Transference: Training Graph Neural Networks on Growing Graphs

Graph neural networks (GNNs) use graph convolutions to exploit network invariances and learn meaningful feature representations from network data. However, on large-scale graphs convolutions incur in high computational cost, leading to scalability limitations. Leveraging the graphon -- the limit object of a graph -- in this paper we consider the problem of learning a graphon neural network (WNN) -- the limit object of a GNN -- by training GNNs on graphs sampled from the graphon. Under smoothness conditions, we show that: (i) the expected distance between the learning steps on the GNN and on the WNN decreases asymptotically with the size of the graph, and (ii) when training on a sequence of growing graphs, gradient descent follows the learning direction of the WNN. Inspired by these results, we propose a novel algorithm to learn GNNs on large-scale graphs that, starting from a moderate number of nodes, successively increases the size of the graph during training. This algorithm is further benchmarked on a decentralized control problem, where it retains comparable performance to its large-scale counterpart at a reduced computational cost.

preprint2022arXiv

Learning Connectivity-Maximizing Network Configurations

In this letter we propose a data-driven approach to optimizing the algebraic connectivity of a team of robots. While a considerable amount of research has been devoted to this problem, we lack a method that scales in a manner suitable for online applications for more than a handful of agents. To that end, we propose a supervised learning approach with a convolutional neural network (CNN) that learns to place communication agents from an expert that uses an optimization-based strategy. We demonstrate the performance of our CNN on canonical line and ring topologies, 105k randomly generated test cases, and larger teams not seen during training. We also show how our system can be applied to dynamic robot teams through a Unity-based simulation. After training, our system produces connected configurations over an order of magnitude faster than the optimization-based scheme for teams of 10-20 agents.

preprint2022arXiv

Learning Decentralized Wireless Resource Allocations with Graph Neural Networks

We consider the broad class of decentralized optimal resource allocation problems in wireless networks, which can be formulated as a constrained statistical learning problems with a localized information structure. We develop the use of Aggregation Graph Neural Networks (Agg-GNNs), which process a sequence of delayed and potentially asynchronous graph aggregated state information obtained locally at each transmitter from multi-hop neighbors. We further utilize model-free primal-dual learning methods to optimize performance subject to constraints in the presence of delay and asynchrony inherent to decentralized networks. We demonstrate a permutation equivariance property of the resulting resource allocation policy that can be shown to facilitate transference to dynamic network configurations. The proposed framework is validated with numerical simulations that exhibit superior performance to baseline strategies.

preprint2022arXiv

Learning Graph Structure from Convolutional Mixtures

Machine learning frameworks such as graph neural networks typically rely on a given, fixed graph to exploit relational inductive biases and thus effectively learn from network data. However, when said graphs are (partially) unobserved, noisy, or dynamic, the problem of inferring graph structure from data becomes relevant. In this paper, we postulate a graph convolutional relationship between the observed and latent graphs, and formulate the graph learning task as a network inverse (deconvolution) problem. In lieu of eigendecomposition-based spectral methods or iterative optimization solutions, we unroll and truncate proximal gradient iterations to arrive at a parameterized neural network architecture that we call a Graph Deconvolution Network (GDN). GDNs can learn a distribution of graphs in a supervised fashion, perform link prediction or edge-weight regression tasks by adapting the loss function, and they are inherently inductive. We corroborate GDN's superior graph recovery performance and its generalization to larger graphs using synthetic data in supervised settings. Furthermore, we demonstrate the robustness and representation power of GDNs on real world neuroimaging and social network datasets.

preprint2022arXiv

Learning Optimal Resource Allocations in Wireless Systems

This paper considers the design of optimal resource allocation policies in wireless communication systems which are generically modeled as a functional optimization problem with stochastic constraints. These optimization problems have the structure of a learning problem in which the statistical loss appears as a constraint, motivating the development of learning methodologies to attempt their solution. To handle stochastic constraints, training is undertaken in the dual domain. It is shown that this can be done with small loss of optimality when using near-universal learning parameterizations. In particular, since deep neural networks (DNN) are near-universal their use is advocated and explored. DNNs are trained here with a model-free primal-dual method that simultaneously learns a DNN parametrization of the resource allocation policy and optimizes the primal and dual variables. Numerical simulations demonstrate the strong performance of the proposed approach on a number of common wireless resource allocation problems.

preprint2022arXiv

Model-Free Design of Control Systems over Wireless Fading Channels

Wireless control systems replace traditional wired communication with wireless networks to exchange information between actuators, plants and sensors in a control system. The noise in wireless channels renders ideal control policies suboptimal, and their performance is moreover directly dependent on the way in which wireless resources are allocated between control loops. Proper design of the control policy and the resource allocation policy based on both plant states and wireless fading states is then critical to achieve good performance. The resulting problem of co-designing control-aware resource allocation policies and communication-aware controllers, however, is challenging due to its infinite dimensionality, existence of system constraints and need for explicit knowledge of the plants and wireless network models. To overcome those challenges, we rely on constrained reinforcement learning algorithms to propose a model-free approach to the design of wireless control systems. We demonstrate the near optimality of control system performance and stability using near-universal policy parametrizations and present a practical model-free algorithm to learn the co-design policy. Numerical experiments show the strong performance of learned policies over baseline solutions.

preprint2022arXiv

Navigation of a Quadratic Potential with Ellipsoidal Obstacles

Given a convex quadratic potential of which its minimum is the agent's goal and a Euclidean space populated with ellipsoidal obstacles, one can construct a Rimon-Koditschek (RK) artificial potential to navigate. Its negative gradient attracts the agent toward the goal and repels the agent away from the boundary of the obstacles. This is a popular approach to navigation problems since it can be implemented with local spatial information that is acquired during operation time. However, navigation is only successful in situations where the obstacles are not too eccentric (flat). This paper proposes a modification to gradient dynamics that allows successful navigation of an environment with a quadratic cost and ellipsoidal obstacles regardless of their eccentricity. This is accomplished by altering gradient dynamics with a Hessian correction that is intended to imitate worlds with spherical obstacles in which RK potentials are known to work. The resulting dynamics simplify by the quadratic form of the obstacles. Convergence to the goal and obstacle avoidance is established from almost every initial position (up to a set of measure one) in the free space, with mild conditions on the location of the target. Results are corroborated empirically with numerical simulations.

preprint2022arXiv

Safe Policies for Reinforcement Learning via Primal-Dual Methods

In this paper, we study the learning of safe policies in the setting of reinforcement learning problems. This is, we aim to control a Markov Decision Process (MDP) of which we do not know the transition probabilities, but we have access to sample trajectories through experience. We define safety as the agent remaining in a desired safe set with high probability during the operation time. We therefore consider a constrained MDP where the constraints are probabilistic. Since there is no straightforward way to optimize the policy with respect to the probabilistic constraint in a reinforcement learning framework, we propose an ergodic relaxation of the problem. The advantages of the proposed relaxation are threefold. (i) The safety guarantees are maintained in the case of episodic tasks and they are kept up to a given time horizon for continuing tasks. (ii) The constrained optimization problem despite its non-convexity has arbitrarily small duality gap if the parametrization of the policy is rich enough. (iii) The gradients of the Lagrangian associated with the safe-learning problem can be easily computed using standard policy gradient results and stochastic approximation tools. Leveraging these advantages, we establish that primal-dual algorithms are able to find policies that are safe and optimal. We test the proposed approach in a navigation task in a continuous domain. The numerical results show that our algorithm is capable of dynamically adapting the policy to the environment and the required safety levels.

preprint2022arXiv

Self-Consistency of the Fokker-Planck Equation

The Fokker-Planck equation (FPE) is the partial differential equation that governs the density evolution of the Itô 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.

preprint2022arXiv

Space-Time Graph Neural Networks

We introduce space-time graph neural network (ST-GNN), a novel GNN architecture, tailored to jointly process the underlying space-time topology of time-varying network data. The cornerstone of our proposed architecture is the composition of time and graph convolutional filters followed by pointwise nonlinear activation functions. We introduce a generic definition of convolution operators that mimic the diffusion process of signals over its underlying support. On top of this definition, we propose space-time graph convolutions that are built upon a composition of time and graph shift operators. We prove that ST-GNNs with multivariate integral Lipschitz filters are stable to small perturbations in the underlying graphs as well as small perturbations in the time domain caused by time warping. Our analysis shows that small variations in the network topology and time evolution of a system does not significantly affect the performance of ST-GNNs. Numerical experiments with decentralized control systems showcase the effectiveness and stability of the proposed ST-GNNs.

preprint2022arXiv

Synthesizing Decentralized Controllers with Graph Neural Networks and Imitation Learning

Dynamical systems consisting of a set of autonomous agents face the challenge of having to accomplish a global task, relying only on local information. While centralized controllers are readily available, they face limitations in terms of scalability and implementation, as they do not respect the distributed information structure imposed by the network system of agents. Given the difficulties in finding optimal decentralized controllers, we propose a novel framework using graph neural networks (GNNs) to \emph{learn} these controllers. GNNs are well-suited for the task since they are naturally distributed architectures and exhibit good scalability and transferability properties. We show that GNNs learn appropriate decentralized controllers by means of imitation learning, leverage their permutation invariance properties to successfully scale to larger teams and transfer to unseen scenarios at deployment time. The problems of flocking and multi-agent path planning are explored to illustrate the potential of GNNs in learning decentralized controllers.

preprint2022arXiv

Training Stable Graph Neural Networks Through Constrained Learning

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.

preprint2022arXiv

Wide and Deep Graph Neural Network with Distributed Online Learning

Graph neural networks (GNNs) are naturally distributed architectures for learning representations from network data. This renders them suitable candidates for decentralized tasks. In these scenarios, the underlying graph often changes with time due to link failures or topology variations, creating a mismatch between the graphs on which GNNs were trained and the ones on which they are tested. Online learning can be leveraged to retrain GNNs at testing time to overcome this issue. However, most online algorithms are centralized and usually offer guarantees only on convex problems, which GNNs rarely lead to. This paper develops the Wide and Deep GNN (WD-GNN), a novel architecture that can be updated with distributed online learning mechanisms. The WD-GNN consists of two components: the wide part is a linear graph filter and the deep part is a nonlinear GNN. At training time, the joint wide and deep architecture learns nonlinear representations from data. At testing time, the wide, linear part is retrained, while the deep, nonlinear one remains fixed. This often leads to a convex formulation. We further propose a distributed online learning algorithm that can be implemented in a decentralized setting. We also show the stability of the WD-GNN to changes of the underlying graph and analyze the convergence of the proposed online learning procedure. Experiments on movie recommendation, source localization and robot swarm control corroborate theoretical findings and show the potential of the WD-GNN for distributed online learning.

preprint2021arXiv

Graph Neural Networks: Architectures, Stability and Transferability

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 with 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 number of nodes. Concepts are illustrated by the application of GNNs to recommendation systems, decentralized collaborative control, and wireless communication networks.

preprint2021arXiv

Large Scale Distributed Collaborative Unlabeled Motion Planning with Graph Policy Gradients

In this paper, we present a learning method to solve the unlabelled motion problem with motion constraints and space constraints in 2D space for a large number of robots. To solve the problem of arbitrary dynamics and constraints we propose formulating the problem as a multi-agent problem. We are able to demonstrate the scalability of our methods for a large number of robots by employing a graph neural network (GNN) to parameterize policies for the robots. The GNN reduces the dimensionality of the problem by learning filters that aggregate information among robots locally, similar to how a convolutional neural network is able to learn local features in an image. Additionally, by employing a GNN we are also able to overcome the computational overhead of training policies for a large number of robots by first training graph filters for a small number of robots followed by zero-shot policy transfer to a larger number of robots. We demonstrate the effectiveness of our framework through various simulations.

preprint2021arXiv

Nonlinear State-Space Generalizations of Graph Convolutional Neural Networks

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.

preprint2021arXiv

Probably Approximately Correct Constrained Learning

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.

preprint2021arXiv

ROS-NetSim: A Framework for the Integration of Robotic and Network Simulators

Multi-agent systems play an important role in modern robotics. Due to the nature of these systems, coordination among agents via communication is frequently necessary. Indeed, Perception-Action-Communication (PAC) loops, or Perception-Action loops closed over a communication channel, are a critical component of multi-robot systems. However, we lack appropriate tools for simulating PAC loops. To that end, in this paper, we introduce ROS-NetSim, a ROS package that acts as an interface between robotic and network simulators. With ROS-NetSim, we can attain high-fidelity representations of both robotic and network interactions by accurately simulating the PAC loop. Our proposed approach is lightweight, modular and adaptive. Furthermore, it can be used with many available network and physics simulators by making use of our proposed interface. In summary, ROS-NetSim is (i) Transparent to the ROS target application, (ii) Agnostic to the specific network and physics simulator being used, and (iii) Tunable in fidelity and complexity. As part of our contribution, we have made available an open-source implementation of ROS-NetSim to the community.

preprint2021arXiv

Stability of Neural Networks on Riemannian Manifolds

Convolutional Neural Networks (CNNs) have been applied to data with underlying non-Euclidean structures and have achieved impressive successes. This brings the stability analysis of CNNs on non-Euclidean domains into notice because CNNs have been proved stable on Euclidean domains. This paper focuses on the stability of CNNs on Riemannian manifolds. By taking the Laplace-Beltrami operators into consideration, we construct an $α$-frequency difference threshold filter to help separate the spectrum of the operator with an infinite dimensionality. We further construct a manifold neural network architecture with these filters. We prove that both the manifold filters and neural networks are stable under absolute perturbations to the operators. The results also implicate a trade-off between the stability and discriminability of manifold neural networks. Finally we verify our conclusions with numerical experiments in a wireless adhoc network scenario.

preprint2021arXiv

Sufficiently Accurate Model Learning for Planning

Data driven models of dynamical systems help planners and controllers to provide more precise and accurate motions. Most model learning algorithms will try to minimize a loss function between the observed data and the model's predictions. This can be improved using prior knowledge about the task at hand, which can be encoded in the form of constraints. This turns the unconstrained model learning problem into a constrained one. These constraints allow models with finite capacity to focus their expressive power on important aspects of the system. This can lead to models that are better suited for certain tasks. This paper introduces the constrained Sufficiently Accurate model learning approach, provides examples of such problems, and presents a theorem on how close some approximate solutions can be. The approximate solution quality will depend on the function parameterization, loss and constraint function smoothness, and the number of samples in model learning.

preprint2020arXiv

Approximate Supermodularity of Kalman Filter Sensor Selection

This work considers the problem of selecting sensors in a large scale system to minimize the error in estimating its states. More specifically, the state estimation mean-square error(MSE) and worst-case error for Kalman filtering and smoothing. Such selection problems are in general NP-hard, i.e., their solution can only be approximated in practice even for moderately large problems. Due to its low complexity and iterative nature, greedy algorithms are often used to obtain these approximations by selecting one sensor at a time choosing at each step the one that minimizes the estimation performance metric. When this metric is supermodular, this solution is guaranteed to be (1-1/e)-optimal. This is however not the case for the MSE or the worst-case error. This issue is often circumvented by using supermodular surrogates, such as the logdet, despite the fact that minimizing the logdet is not equivalent to minimizing the MSE. Here, this issue is addressed by leveraging the concept of approximate supermodularity to derive near-optimality certificates for greedily minimizing the estimation mean-square and worst-case error. In typical application scenarios, these certificates approach the (1-1/e) guarantee obtained for supermodular functions, thus demonstrating that no change to the original problem is needed to obtain guaranteed good performance.

preprint2020arXiv

Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems

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-size is required for exact asymptotic convergence with the fact that constant step-size learns faster in finite time up to an error. To do so, rather than fixing the mini-batch and the 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 developed for both convex and non-convex stochastic optimization problems. It inherits 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 computational cost. Experimentally, we observe that TSA attains a favorable tradeoff relative to standard SGD that fixes the mini-batch and the step-size, or simply allowing one to increase or decrease respectively.

preprint2020arXiv

Counterfactual Programming for Optimal Control

In recent years, considerable work has been done to tackle the issue of designing control laws based on observations to allow unknown dynamical systems to perform pre-specified tasks. At least as important for autonomy, however, is the issue of learning which tasks can be performed in the first place. This is particularly critical in situations where multiple (possibly conflicting) tasks and requirements are demanded from the agent, resulting in infeasible specifications. Such situations arise due to over-specification or dynamic operating conditions and are only aggravated when the dynamical system model is learned through simulations. Often, these issues are tackled using regularization and penalties tuned based on application-specific expert knowledge. Nevertheless, this solution becomes impractical for large-scale systems, unknown operating conditions, and/or in online settings where expert input would be needed during the system operation. Instead, this work enables agents to autonomously pose, tune, and solve optimal control problems by compromising between performance and specification costs. Leveraging duality theory, it puts forward a counterfactual optimization algorithm that directly determines the specification trade-off while solving the optimal control problem.

preprint2020arXiv

Efficient Distributed Hessian Free Algorithm for Large-scale Empirical Risk Minimization via Accumulating Sample Strategy

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.

preprint2020arXiv

Federated Classification using Parsimonious Functions in Reproducing Kernel Hilbert Spaces

Federated learning forms a global model using data collected from a federation agent. This type of learning has two main challenges: the agents generally don't collect data over the same distribution, and the agents have limited capabilities of storing and transmitting data. Therefore, it is impractical for each agent to send the entire data over the network. Instead, each agent must form a local model and decide what information is fundamental to the learning problem, which will be sent to a central unit. The central unit can then form the global model using only the information received from the agents. We propose a method that tackles these challenges. First each agent forms a local model using a low complexity reproducing kernel Hilbert space representation. From the model the agents identify the fundamental samples which are sent to the central unit. The fundamental samples are obtained by solving the dual problem. The central unit then forms the global model. We show that the solution of the federated learner converges to that of the centralized learner asymptotically as the sample size increases. The performance of the proposed algorithm is evaluated using experiments with both simulated data and real data sets from an activity recognition task, for which the data is collected from a wearable device. The experimentation results show that the accuracy of our method converges to that of a centralized learner with increasing sample size.

preprint2020arXiv

Functional Nonlinear Sparse Models

Signal processing is rich in inherently continuous and often nonlinear applications, such as spectral estimation, optical imaging, and super-resolution microscopy, in which sparsity plays a key role in obtaining state-of-the-art results. Coping with the infinite dimensionality and non-convexity of these problems typically involves discretization and convex relaxations, e.g., using atomic norms. Nevertheless, grid mismatch and other coherence issues often lead to discretized versions of sparse signals that are not sparse. Even if they are, recovering sparse solutions using convex relaxations requires assumptions that may be hard to meet in practice. What is more, problems involving nonlinear measurements remain non-convex even after relaxing the sparsity objective. We address these issues by directly tackling the continuous, nonlinear problem cast as a sparse functional optimization program. We prove that when these problems are non-atomic, they have no duality gap and can therefore be solved efficiently using duality and~(stochastic) convex optimization methods. We illustrate the wide range of applications of this approach by formulating and solving problems from nonlinear spectral estimation and robust classification.

preprint2020arXiv

Graph Neural Networks for Decentralized Multi-Robot Path Planning

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).

preprint2020arXiv

Graph-Adaptive Activation Functions for Graph Neural Networks

Activation functions are crucial in graph neural networks (GNNs) as they allow defining a nonlinear family of functions to capture the relationship between the input graph data and their representations. This paper proposes activation functions for GNNs that not only adapt to the graph into the nonlinearity, but are also distributable. To incorporate the feature-topology coupling into all GNN components, nodal features are nonlinearized and combined with a set of trainable parameters in a form akin to graph convolutions. The latter leads to a graph-adaptive trainable nonlinear component of the GNN that can be implemented directly or via kernel transformations, therefore, enriching the class of functions to represent the network data. Whether in the direct or kernel form, we show permutation equivariance is always preserved. We also prove the subclass of graph-adaptive max activation functions are Lipschitz stable to input perturbations. Numerical experiments with distributed source localization, finite-time consensus, distributed regression, and recommender systems corroborate our findings and show improved performance compared with pointwise as well as state-of-the-art localized nonlinearities.

preprint2020arXiv

Graphon Pooling in Graph Neural Networks

Graph neural networks (GNNs) have been used effectively in different applications involving the processing of signals on irregular structures modeled by graphs. Relying on the use of shift-invariant graph filters, GNNs extend the operation of convolution to graphs. However, the operations of pooling and sampling are still not clearly defined and the approaches proposed in the literature either modify the graph structure in a way that does not preserve its spectral properties, or require defining a policy for selecting which nodes to keep. In this work, we propose a new strategy for pooling and sampling on GNNs using graphons which preserves the spectral properties of the graph. To do so, we consider the graph layers in a GNN as elements of a sequence of graphs that converge to a graphon. In this way we have no ambiguity in the node labeling when mapping signals from one layer to the other and a spectral representation that is consistent throughout the layers. We evaluate this strategy in a synthetic and a real-world numerical experiment where we show that graphon pooling GNNs are less prone to overfitting and improve upon other pooling techniques, especially when the dimensionality reduction ratios between layers is large.

preprint2020arXiv

Mobile Wireless Network Infrastructure on Demand

In this work, we introduce Mobile Wireless In-frastructure 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.

preprint2020arXiv

Optimal Wireless Resource Allocation with Random Edge Graph Neural Networks

We consider the problem of optimally allocating resources across a set of transmitters and receivers in a wireless network. The resulting optimization problem takes the form of constrained statistical learning, in which solutions can be found in a model-free manner by parameterizing the resource allocation policy. Convolutional neural networks architectures are an attractive option for parameterization, as their dimensionality is small and does not scale with network size. We introduce the random edge graph neural network (REGNN), which performs convolutions over random graphs formed by the fading interference patterns in the wireless network. The REGNN-based allocation policies are shown to retain an important permutation equivariance property that makes them amenable to transference to different networks. We further present an unsupervised model-free primal-dual learning algorithm to train the weights of the REGNN. Through numerical simulations, we demonstrate the strong performance REGNNs obtain relative to heuristic benchmarks and their transference capabilities.

preprint2020arXiv

Policy Evaluation in Continuous MDPs with Efficient Kernelized Gradient Temporal Difference

We consider policy evaluation in infinite-horizon discounted Markov decision problems (MDPs) with infinite spaces. We reformulate this task a compositional stochastic program with a function-valued decision variable that belongs to a reproducing kernel Hilbert space (RKHS). We approach this problem via a new functional generalization of stochastic quasi-gradient methods operating in tandem with stochastic sparse subspace projections. The result is an extension of gradient temporal difference learning that yields nonlinearly parameterized value function estimates of the solution to the Bellman evaluation equation. Our main contribution is a memory-efficient non-parametric stochastic method guaranteed to converge exactly to the Bellman fixed point with probability $1$ with attenuating step-sizes. Further, with constant step-sizes, we obtain mean convergence to a neighborhood and that the value function estimates have finite complexity. In the Mountain Car domain, we observe faster convergence to lower Bellman error solutions than existing approaches with a fraction of the required memory.

preprint2020arXiv

Resilient Control: Compromising to Adapt

In optimal control problems, disturbances are typically dealt with using robust solutions, such as H-infinity or tube model predictive control, that plan control actions feasible for the worst-case disturbance. Yet, planning for every contingency can lead to over-conservative, poorly performing solutions or even, in extreme cases, to infeasibility. Resilience addresses these shortcomings by adapting the underlying control problem, e.g., by relaxing its specifications, to obtain a feasible, possibly still valuable trajectory. Despite their different aspects, robustness and resilience are often conflated in the context of dynamical systems and control. The goal of this paper is to formalize, in the context of optimal control, the concept of resilience understood as above, i.e., in terms of adaptation. To do so, we introduce a resilient formulation of optimal control by allowing disruption-dependent modifications of the requirements that induce the desired resilient behavior. We then propose a framework to design these behaviors automatically by trading off control performance and requirement violations. We analyze this resilience-by-compromise method to obtain inverse optimality results and quantify the effect of disturbances on the induced requirement relaxations. By proving that robustness and resilience optimize different objectives, we show that these are in fact distinct system properties. We conclude by illustrating the effect of resilience in different control problems.

preprint2020arXiv

Resource Allocation via Graph Neural Networks in Free Space Optical Fronthaul 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.

preprint2020arXiv

Sinkhorn Barycenter via Functional Gradient Descent

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 Sinkhorn Descent (SD). We prove that 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 SD preserves the weak convergence of empirical measures. Importantly, the computational complexity of SD scales linearly in the dimension $d$ and we demonstrate its scalability by solving a $100$-dimensional Sinkhorn barycenter problem.

preprint2020arXiv

Sufficiently Accurate Model Learning

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.

preprint2020arXiv

The empirical duality gap of constrained statistical learning

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.

preprint2020arXiv

Wireless Power Control via Counterfactual Optimization of Graph Neural Networks

We consider the problem of downlink power control in wireless networks, consisting of multiple transmitter-receiver pairs communicating with each other over a single shared wireless medium. To mitigate the interference among concurrent transmissions, we leverage the network topology to create a graph neural network architecture, and we then use an unsupervised primal-dual counterfactual optimization approach to learn optimal power allocation decisions. We show how the counterfactual optimization technique allows us to guarantee a minimum rate constraint, which adapts to the network size, hence achieving the right balance between average and $5^{th}$ percentile user rates throughout a range of network configurations.

preprint2020arXiv

Zeroth-order Deterministic Policy Gradient

Deterministic Policy Gradient (DPG) removes a level of randomness from standard randomized-action Policy Gradient (PG), and demonstrates substantial empirical success for tackling complex dynamic problems involving Markov decision processes. At the same time, though, DPG loses its ability to learn in a model-free (i.e., actor-only) fashion, frequently necessitating the use of critics in order to obtain consistent estimates of the associated policy-reward gradient. In this work, we introduce Zeroth-order Deterministic Policy Gradient (ZDPG), which approximates policy-reward gradients via two-point stochastic evaluations of the $Q$-function, constructed by properly designed low-dimensional action-space perturbations. Exploiting the idea of random horizon rollouts for obtaining unbiased estimates of the $Q$-function, ZDPG lifts the dependence on critics and restores true model-free policy learning, while enjoying built-in and provable algorithmic stability. Additionally, we present new finite sample complexity bounds for ZDPG, which improve upon existing results by up to two orders of magnitude. Our findings are supported by several numerical experiments, which showcase the effectiveness of ZDPG in a practical setting, and its advantages over both PG and Baseline PG.

preprint2019arXiv

A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization

We introduce the primal-dual quasi-Newton (PD-QN) method as an approximated second order method for solving decentralized optimization problems. The PD-QN method performs quasi-Newton updates on both the primal and dual variables of the consensus optimization problem to find the optimal point of the augmented Lagrangian. By optimizing the augmented Lagrangian, the PD-QN method is able to find the exact solution to the consensus problem with a linear rate of convergence. We derive fully decentralized quasi-Newton updates that approximate second order information to reduce the computational burden relative to dual methods and to make the method more robust in ill-conditioned problems relative to first order methods. The linear convergence rate of PD-QN is established formally and strong performance advantages relative to existing dual and primal-dual methods are shown numerically.

preprint2019arXiv

Controllability of Bandlimited Graph Processes Over Random Time Varying Graphs

Controllability of complex networks arises in many technological problems involving social, financial, road, communication, and smart grid networks. In many practical situations, the underlying topology might change randomly with time, due to link failures such as changing friendships, road blocks or sensor malfunctions. Thus, it leads to poorly controlled dynamics if randomness is not properly accounted for. We consider the problem of controlling the network state when the topology varies randomly with time. Our problem concerns target states that are bandlimited over the graph; these are states that have nonzero frequency content only on a specific graph frequency band. We thus leverage graph signal processing and exploit the bandlimited model to drive the network state from a fixed set of control nodes. When controlling the state from a few nodes, we observe that spurious, out-of-band frequency content is created. Therefore, we focus on controlling the network state over the desired frequency band, and then use a graph filter to get rid of the unwanted frequency content. To account for the topological randomness, we develop the concept of controllability in the mean, which consists of driving the expected network state towards the target state. A detailed mean squared error analysis is performed to quantify the statistical deviation between the final controlled state on a particular graph realization and the actual target state. Finally, we propose different control strategies and evaluate their effectiveness on synthetic network models and social networks.

preprint2019arXiv

Distributed Constrained Online Learning

In this paper, we consider groups of agents in a network that select actions in order to satisfy a set of constraints that vary arbitrarily over time and minimize a time-varying function of which they have only local observations. The selection of actions, also called a strategy, is causal and decentralized, i.e., the dynamical system that determines the actions of a given agent depends only on the constraints at the current time and on its own actions and those of its neighbors. To determine such a strategy, we propose a decentralized saddle point algorithm and show that the corresponding global fit and regret are bounded by functions of the order of $\sqrt{T}$. Specifically, we define the global fit of a strategy as a vector that integrates over time the global constraint violations as seen by a given node. The fit is a performance loss associated with online operation as opposed to offline clairvoyant operation which can always select an action if one exists, that satisfies the constraints at all times. If this fit grows sublinearly with the time horizon it suggests that the strategy approaches the feasible set of actions. Likewise, we define the regret of a strategy as the difference between its accumulated cost and that of the best fixed action that one could select knowing beforehand the time evolution of the objective function. Numerical examples support the theoretical conclusions.

preprint2019arXiv

Invariance-Preserving Localized Activation Functions for Graph Neural Networks

Graph signals are signals with an irregular structure that can be described by a graph. Graph neural networks (GNNs) are information processing architectures tailored to these graph signals and made of stacked layers that compose graph convolutional filters with nonlinear activation functions. Graph convolutions endow GNNs with invariance to permutations of the graph nodes' labels. In this paper, we consider the design of trainable nonlinear activation functions that take into consideration the structure of the graph. This is accomplished by using graph median filters and graph max filters, which mimic linear graph convolutions and are shown to retain the permutation invariance of GNNs. We also discuss modifications to the backpropagation algorithm necessary to train local activation functions. The advantages of localized activation function architectures are demonstrated in four numerical experiments: source localization on synthetic graphs, authorship attribution of 19th century novels, movie recommender systems and scientific article classification. In all cases, localized activation functions are shown to improve model capacity.

preprint2016arXiv

A Class of Parallel Doubly Stochastic Algorithms for Large-Scale Learning

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. We call the algorithm stochastic because processors choose training subsets uniformly at random. 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 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.

preprint2016arXiv

A Decentralized Quasi-Newton Method for Dual Formulations of Consensus Optimization

This paper considers consensus optimization problems where each node of a network has access to a different summand of an aggregate cost function. Nodes try to minimize the aggregate cost function, while they exchange information only with their neighbors. We modify the dual decomposition method to incorporate a curvature correction inspired by the Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi-Newton method. The resulting dual D-BFGS method is a fully decentralized algorithm in which nodes approximate curvature information of themselves and their neighbors through the satisfaction of a secant condition. Dual D-BFGS is of interest in consensus optimization problems that are not well conditioned, making first order decentralized methods ineffective, and in which second order information is not readily available, making decentralized second order methods infeasible. Asynchronous implementation is discussed and convergence of D-BFGS is established formally for both synchronous and asynchronous implementations. Performance advantages relative to alternative decentralized algorithms are shown numerically.

preprint2016arXiv

A Decentralized Second-Order Method for Dynamic Optimization

This paper considers decentralized dynamic optimization problems where nodes of a network try to minimize a sequence of time-varying objective functions in a real-time scheme. At each time slot, nodes have access to different summands of an instantaneous global objective function and they are allowed to exchange information only with their neighbors. This paper develops the application of the Exact Second-Order Method (ESOM) to solve the dynamic optimization problem in a decentralized manner. The proposed dynamic ESOM algorithm operates by primal descending and dual ascending on a quadratic approximation of an augmented Lagrangian of the instantaneous consensus optimization problem. The convergence analysis of dynamic ESOM indicates that a Lyapunov function of the sequence of primal and dual errors converges linearly to an error bound when the local functions are strongly convex and have Lipschitz continuous gradients. Numerical results demonstrate the claim that the sequence of iterates generated by the proposed method is able to track the sequence of optimal arguments.

preprint2016arXiv

A Decentralized Second-Order Method with Exact Linear Convergence Rate for Consensus Optimization

This paper considers decentralized consensus optimization problems where different summands of a global objective function are available at nodes of a network that can communicate with neighbors only. The proximal method of multipliers is considered as a powerful tool that relies on proximal primal descent and dual ascent updates on a suitably defined augmented Lagrangian. The structure of the augmented Lagrangian makes this problem non-decomposable, which precludes distributed implementations. This problem is regularly addressed by the use of the alternating direction method of multipliers. The exact second order method (ESOM) is introduced here as an alternative that relies on: (i) The use of a separable quadratic approximation of the augmented Lagrangian. (ii) A truncated Taylor's series to estimate the solution of the first order condition imposed on the minimization of the quadratic approximation of the augmented Lagrangian. The sequences of primal and dual variables generated by ESOM are shown to converge linearly to their optimal arguments when the aggregate cost function is strongly convex and its gradients are Lipschitz continuous. Numerical results demonstrate advantages of ESOM relative to decentralized alternatives in solving least squares and logistic regression problems.

preprint2016arXiv

Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy

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 and empirically that Ada Newton can double the size of the training set in each iteration to achieve the statistical accuracy of the full training set with about two passes over the dataset.

preprint2016arXiv

Admissible Hierarchical Clustering Methods and Algorithms for Asymmetric Networks

This paper characterizes hierarchical clustering methods that abide by two previously introduced axioms -- thus, denominated admissible methods -- and proposes tractable algorithms for their implementation. We leverage the fact that, for asymmetric networks, every admissible method must be contained between reciprocal and nonreciprocal clustering, and describe three families of intermediate methods. Grafting methods exchange branches between dendrograms generated by different admissible methods. The convex combination family combines admissible methods through a convex operation in the space of dendrograms, and thirdly, the semi-reciprocal family clusters nodes that are related by strong cyclic influences in the network. Algorithms for the computation of hierarchical clusters generated by reciprocal and nonreciprocal clustering as well as the grafting, convex combination, and semi-reciprocal families are derived using matrix operations in a dioid algebra. Finally, the introduced clustering methods and algorithms are exemplified through their application to a network describing the interrelation between sectors of the United States (U.S.) economy.

preprint2016arXiv

Brain network efficiency is influenced by pathological source of corticobasal syndrome

Multimodal neuroimaging studies of corticobasal syndrome using volumetric MRI and DTI successfully discriminate between Alzheimer's disease and frontotemporal lobar degeneration but this evidence has typically included clinically heterogeneous patient cohorts and has rarely assessed the network structure of these distinct sources of pathology. Using structural MRI data, we identify areas in fronto-temporo-parietal cortex with reduced gray matter density in corticobasal syndrome relative to age matched controls. A support vector machine procedure demonstrates that gray matter density poorly discriminates between frontotemporal lobar degeneration and Alzheimer's disease pathology subgroups with low sensitivity and specificity. In contrast, a statistic of local network efficiency demonstrates excellent discriminatory power, with high sensitivity and specificity. Our results indicate that the underlying pathological sources of corticobasal syndrome can be classified more accurately using graph theoretical statistics of white matter microstructure in association cortex than by regional gray matter density alone. These results highlight the importance of a multimodal neuroimaging approach to diagnostic analyses of corticobasal syndrome and suggest that distinct sources of pathology mediate the circuitry of brain regions affected by corticobasal syndrome.

preprint2016arXiv

Decentralized Dynamic Discriminative Dictionary Learning

We consider discriminative dictionary learning in a distributed online setting, where a network of agents aims to learn a common set of dictionary elements of a feature space and model parameters while sequentially receiving observations. 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. Using Lagrange multipliers to penalize the discrepancy between them, only neighboring nodes exchange model information. We show that decisions made with this saddle point algorithm asymptotically achieve a first-order stationarity condition on average.

preprint2016arXiv

Decentralized Prediction-Correction Methods for Networked Time-Varying Convex Optimization

We develop algorithms that find and track the optimal solution trajectory of time-varying convex optimization problems which consist of local and network-related objectives. The algorithms are derived from the prediction-correction methodology, which corresponds to a strategy where the time-varying problem is sampled at discrete time instances and then a sequence is generated via alternatively executing predictions on how the optimizers at the next time sample are changing and corrections on how they actually have changed. Prediction is based on how the optimality conditions evolve in time, while correction is based on a gradient or Newton method, leading to Decentralized Prediction-Correction Gradient (DPC-G) and Decentralized Prediction-Correction Newton (DPC-N). We extend these methods to cases where the knowledge on how the optimization programs are changing in time is only approximate and propose Decentralized Approximate Prediction-Correction Gradient (DAPC-G) and Decentralized Approximate Prediction-Correction Newton (DAPC-N). Convergence properties of all the proposed methods are studied and empirical performance is shown on an application of a resource allocation problem in a wireless network. We observe that the proposed methods outperform existing running algorithms by orders of magnitude. The numerical results showcase a trade-off between convergence accuracy, sampling period, and network communications.

preprint2016arXiv

Demand Response with Communicating Rational Consumers

The performance of an energy system under a real-time pricing mechanism depends on the consumption behavior of its customers, which involves uncertainties. In this paper, we consider a system operator that charges its customers with a real-time price that depends on the total realized consumption. Customers have unknown and heterogeneous consumption preferences. We propose behavior models in which customers act selfishly, altruistically or as welfare-maximizers. In addition, we consider information models where customers keep their consumption levels private, communicate with a neighboring set of customers, or receive broadcasted demand from the operator. Our analysis focuses on the dispersion of the system performance under different consumption models. To this end, for each pair of behavior and information model we define and characterize optimal rational behavior, and provide a local algorithm that can be implemented by the consumption scheduler devices. Analytical comparisons of the two extreme information models, namely, private and complete information models, show that communication model reduces demand uncertainty while having negligible effect on aggregate consumer utility and welfare. In addition, we show the impact of real-time price policy parameters have on the expected welfare loss due to selfish behavior affording critical policy insights.

preprint2016arXiv

Distributed Fictitious Play for Optimal Behavior of Multi-Agent Systems with Incomplete Information

A multi-agent system operates in an uncertain environment about which agents have different and time varying beliefs that, as time progresses, converge to a common belief. A global utility function that depends on the realized state of the environment and actions of all the agents determines the system's optimal behavior. We define the asymptotically optimal action profile as an equilibrium of the potential game defined by considering the expected utility with respect to the asymptotic belief. At finite time, however, agents have not entirely congruous beliefs about the state of the environment and may select conflicting actions. This paper proposes a variation of the fictitious play algorithm which is proven to converge to equilibrium actions if the state beliefs converge to a common distribution at a rate that is at least linear. In conventional fictitious play, agents build beliefs on others' future behavior by computing histograms of past actions and best respond to their expected payoffs integrated with respect to these histograms. In the variations developed here histograms are built using knowledge of actions taken by nearby nodes and best responses are further integrated with respect to the local beliefs on the state of the environment. We exemplify the use of the algorithm in coordination and target covering games.

preprint2016arXiv

Doubly Random Parallel Stochastic Methods for Large Scale Learning

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 processors to operate in a randomly chosen subset of blocks of the feature vector. We call the algorithm parallel stochastic because processors choose elements of the training set randomly and independently. 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 convex. In particular, we show that: (i) When using decreasing stepsizes, RAPSA converges almost surely over the random choice of blocks and functions. (ii) When using constant stepsizes, convergence is to a neighborhood of optimality with a rate that is linear in expectation. RAPSA is numerically evaluated on the MNIST digit recognition problem.

preprint2016arXiv

Excisive Hierarchical Clustering Methods for Network Data

We introduce two practical properties of hierarchical clustering methods for (possibly asymmetric) network data: excisiveness and linear scale preservation. The latter enforces imperviousness to change in units of measure whereas the former ensures local consistency of the clustering outcome. Algorithmically, excisiveness implies that we can reduce computational complexity by only clustering a data subset of interest while theoretically guaranteeing that the same hierarchical outcome would be observed when clustering the whole dataset. Moreover, we introduce the concept of representability, i.e. a generative model for describing clustering methods through the specification of their action on a collection of networks. We further show that, within a rich set of admissible methods, requiring representability is equivalent to requiring both excisiveness and linear scale preservation. Leveraging this equivalence, we show that all excisive and linear scale preserving methods can be factored into two steps: a transformation of the weights in the input network followed by the application of a canonical clustering method. Furthermore, their factorization can be used to show stability of excisive and linear scale preserving methods in the sense that a bounded perturbation in the input network entails a bounded perturbation in the clustering output.

preprint2016arXiv

Functional Alignment with Anatomical Networks is Associated with Cognitive Flexibility

Cognitive flexibility describes the human ability to switch between modes of mental function to achieve goals. Mental switching is accompanied by transient changes in brain activity, which must occur atop an anatomical architecture that bridges disparate cortical and subcortical regions by underlying white matter tracts. However, an integrated perspective regarding how white matter networks might constrain brain dynamics during cognitive processes requiring flexibility has remained elusive. To address this challenge, we applied emerging tools from graph signal processing to decompose BOLD signals based on diffusion imaging tractography in 28 individuals performing a perceptual task that probed cognitive flexibility. We found that the alignment between functional signals and the architecture of the underlying white matter network was associated with greater cognitive flexibility across subjects. Signals with behaviorally-relevant alignment were concentrated in the basal ganglia and anterior cingulate cortex, consistent with cortico-striatal mechanisms of cognitive flexibility. Importantly, these findings are not accessible to unimodal analyses of functional or anatomical neuroimaging alone. Instead, by taking a generalizable and concise reduction of multimodal neuroimaging data, we uncover an integrated structure-function driver of human behavior.

preprint2016arXiv

Graph Frequency Analysis of Brain Signals

This paper presents methods to analyze functional brain networks and signals from graph spectral perspectives. The notion of frequency and filters traditionally defined for signals supported on regular domains such as discrete time and image grids has been recently generalized to irregular graph domains, and 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. We relate graph frequency with principal component analysis when the networks of interest denote functional connectivity. 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 adaptability throughout learning. Further, 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.

preprint2016arXiv

Hierarchical Clustering Given Confidence Intervals of Metric Distances

This paper considers metric spaces where distances between a pair of nodes are represented by distance intervals. The goal is to study methods for the determination of hierarchical clusters, i.e., a family of nested partitions indexed by a resolution parameter, induced from the given distance intervals of the metric spaces. Our construction of hierarchical clustering methods is based on defining admissible methods to be those methods that abide to the axioms of value - nodes in a metric space with two nodes are clustered together at the convex combination of the distance bounds between them - and transformation - when both distance bounds are reduced, the output may become more clustered but not less. Two admissible methods are constructed and are shown to provide universal upper and lower bounds in the space of admissible methods. Practical implications are explored by clustering moving points via snapshots and by clustering networks representing brain structural connectivity using the lower and upper bounds of the network distance. The proposed clustering methods succeed in identifying underlying clustering structures via the maximum and minimum distances in all snapshots, as well as in differentiating brain connectivity networks of patients from those of healthy controls.

preprint2016arXiv

Hierarchical Clustering of Asymmetric Networks

This paper considers networks where relationships between nodes are represented by directed dissimilarities. The goal is to study methods that, based on the dissimilarity structure, output hierarchical clusters, i.e., a family of nested partitions indexed by a connectivity parameter. Our construction of hierarchical clustering methods is built around the concept of admissible methods, which are those that abide by the axioms of value - nodes in a network with two nodes are clustered together at the maximum of the two dissimilarities between them - and transformation - when dissimilarities are reduced, the network may become more clustered but not less. Two particular methods, termed reciprocal and nonreciprocal clustering, are shown to provide upper and lower bounds in the space of admissible methods. Furthermore, alternative clustering methodologies and axioms are considered. In particular, modifying the axiom of value such that clustering in two-node networks occurs at the minimum of the two dissimilarities entails the existence of a unique admissible clustering method.

preprint2016arXiv

Navigation Functions for Convex Potentials in a Space with Convex Obstacles

Given a convex potential in a space with convex obstacles, an artificial potential is used to navigate to the minimum of the natural potential while avoiding collisions. The artificial potential combines the natural potential with potentials that repel the agent from the border of the obstacles. This is a popular approach to navigation problems because it can be implemented with spatially local information that is acquired during operation time. Artificial potentials can, however, have local minima that prevent navigation to the minimum of the natural potential. This paper derives conditions that guarantee artificial potentials have a single minimum that is arbitrarily close to the minimum of the natural potential. The qualitative implication is that artificial potentials succeed when either the condition number-- the ratio of the maximum over the minimum eigenvalue-- of the Hessian of the natural potential is not large and the obstacles are not too flat or when the destination is not close to the border of an obstacle. Numerical analyses explore the practical value of these theoretical conclusions.

preprint2016arXiv

Network Topology Identification from Spectral Templates

Network topology inference is a cornerstone problem in statistical analyses of complex systems. In this context, the fresh look advocated here permeates benefits from convex optimization and graph signal processing, to identify the so-termed graph shift operator (encoding the network topology) given only the eigenvectors of the shift. These spectral templates can be obtained, for example, from principal component analysis of a set of graph signals defined on the particular network. The novel idea is to find a graph shift that while being consistent with the provided spectral information, it endows the network structure with certain desired properties such as sparsity. The focus is on developing efficient recovery algorithms along with identifiability conditions for two particular shifts, the adjacency matrix and the normalized graph Laplacian. Application domains include network topology identification from steady-state signals generated by a diffusion process, and design of a graph filter that facilitates the distributed implementation of a prescribed linear network operator. Numerical tests showcase the effectiveness of the proposed algorithms in recovering synthetic and structural brain networks.

preprint2016arXiv

Network Topology Inference from Spectral Templates

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. The fresh look advocated here permeates benefits from convex optimization and stationarity of graph signals, in order to identify the graph shift operator (a matrix representation of the graph) given only its eigenvectors. These spectral templates can be obtained, e.g., from the sample covariance of independent graph signals diffused on the sought network. The novel idea is to find a graph shift that, while being consistent with the provided spectral information, endows the network with certain desired properties such as sparsity. To that end we develop efficient inference algorithms stemming from provably-tight convex relaxations of natural nonconvex criteria, particularizing the results for two shifts: the adjacency matrix and the normalized Laplacian. Algorithms and theoretical recovery conditions are developed not only when the templates are perfectly known, but also when the eigenvectors are noisy or when only a subset of them are given. Numerical tests showcase the effectiveness of the proposed algorithms in recovering social, brain, and amino-acid networks.

preprint2016arXiv

Online Learning of Feasible Strategies in Unknown Environments

Define an environment as a set of convex constraint functions that vary arbitrarily over time and consider a cost function that is also convex and arbitrarily varying. Agents that operate in this environment intend to select actions that are feasible for all times while minimizing the cost's time average. Such action is said optimal and can be computed offline if the cost and the environment are known a priori. An online policy is one that depends causally on the cost and the environment. To compare online policies to the optimal offline action define the fit of a trajectory as a vector that integrates the constraint violations over time and its regret as the cost difference with the optimal action accumulated over time. Fit measures the extent to which an online policy succeeds in learning feasible actions while regret measures its success in learning optimal actions. This paper proposes the use of online policies computed from a saddle point controller which are shown to have fit and regret that are either bounded or grow at a sublinear rate. These properties provide an indication that the controller finds trajectories that are feasible and optimal in a relaxed sense. Concepts are illustrated throughout with the problem of a shepherd that wants to stay close to all sheep in a herd. Numerical experiments show that the saddle point controller allows the shepherd to do so.

preprint2016arXiv

Online Optimization in Dynamic Environments: Improved Regret Rates for Strongly Convex Problems

In this paper, we address tracking of a time-varying parameter with unknown dynamics. We formalize the problem as an instance of online optimization in a dynamic setting. Using online gradient descent, we propose a method that sequentially predicts the value of the parameter and in turn suffers a loss. The objective is to minimize the accumulation of losses over the time horizon, a notion that is termed dynamic regret. While existing methods focus on convex loss functions, we consider strongly convex functions so as to provide better guarantees of performance. We derive a regret bound that captures the path-length of the time-varying parameter, defined in terms of the distance between its consecutive values. In other words, the bound represents the natural connection of tracking quality to the rate of change of the parameter. We provide numerical experiments to complement our theoretical findings.

preprint2016arXiv

Parsimonious Online Learning with Kernels via Sparse Projections in Function Space

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 tradeoff of objective function evaluation, classification performance, and complexity of the nonparametric regressor extracted the proposed method.

preprint2016arXiv

Persistent Homology Lower Bounds on High Order Network Distances

High order networks are weighted hypergraphs col- lecting relationships between elements of tuples, not necessarily pairs. Valid metric distances between high order networks have been defined but they are difficult to compute when the number of nodes is large. The goal here is to find tractable approximations of these network distances. The paper does so by mapping high order networks to filtrations of simplicial complexes and showing 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 classifying weighted pairwise networks constructed from different gener- ative processes and by comparing the coauthorship networks of engineering and mathematics academic journals. The persistent homology methods succeed in identifying different generative models, in discriminating engineering and mathematics commu- nities, as well as in differentiating engineering communities with different research interests.

preprint2016arXiv

Prediction-Correction Interior-Point Method for Time-Varying Convex Optimization

In this paper, we develop an interior-point method for solving a class of convex optimization problems with time-varying objective and constraint functions. Using log-barrier penalty functions, we propose a continuous-time dynamical system for tracking the (time-varying) optimal solution with an asymptotically vanishing error. This dynamical system is composed of two terms: (i) a correction term consisting of a continuous-time version of Newton's method, and (ii) a prediction term able to track the drift of the optimal solution by taking into account the time-varying nature of the objective and constraint functions. Using appropriately chosen time-varying slack and barrier parameters, we ensure that the solution to this dynamical system globally asymptotically converges to the optimal solution at an exponential rate. We illustrate the applicability of the proposed method in two practical applications: a sparsity promoting least squares problem and a collision-free robot navigation problem.

preprint2016arXiv

Self-Triggered Time-Varying Convex Optimization

In this paper, we propose a self-triggered algorithm to solve a class of convex optimization problems with time-varying objective functions. It is known that the trajectory of the optimal solution can be asymptotically tracked by a continuous-time state update law. Unfortunately, implementing this requires continuous evaluation of the gradient and the inverse Hessian of the objective function which is not amenable to digital implementation. Alternatively, we draw inspiration from self-triggered control to propose a strategy that autonomously adapts the times at which it makes computations about the objective function, yielding a piece-wise affine state update law. The algorithm does so by predicting the temporal evolution of the gradient using known upper bounds on higher order derivatives of the objective function. Our proposed method guarantees convergence to arbitrarily small neighborhood of the optimal trajectory in finite time and without incurring Zeno behavior. We illustrate our framework with numerical simulations.

preprint2016arXiv

Stochastic Artificial Potentials for Online Safe Navigation

Consider a convex set of which we remove an arbitrarily number of disjoints convex sets -- the obstacles -- and a convex function whose minimum is the agent's goal. We consider a local and stochastic approximation of the gradient of a Rimon-Koditschek navigation function where the attractive potential is the convex function that the agent is minimizing. In particular we show that if the estimate available to the agent is unbiased convergence to the desired destination while obstacle avoidance is guaranteed with probability one under the same geometrical conditions than in the deterministic case. Qualitatively these conditions are that the ratio of the maximum over the minimum eigenvalue of the Hessian of the objective function is not too large and that the obstacles are not too flat or too close to the desired destination. Moreover, we show that for biased estimates a similar result holds under some assumptions on the bias. These assumptions are motivated by the study of the estimate of the gradient of a Rimon-Koditschek navigation function for sensor models that fit circles or ellipses around the obstacles. Numerical examples explore the practical value of these theoretical results.

preprint2015arXiv

Decentralized Quadratically Approximated Alternating Direction Method of Multipliers

This paper considers an optimization problem that components of the objective function are available at different nodes of a network and nodes are allowed to only exchange information with their neighbors. The decentralized alternating method of multipliers (DADMM) is a well-established iterative method for solving this category of problems; however, implementation of DADMM requires solving an optimization subproblem at each iteration for each node. This procedure is often computationally costly for the nodes. We introduce a decentralized quadratic approximation of ADMM (DQM) that reduces computational complexity of DADMM by minimizing a quadratic approximation of the objective function. Notwithstanding that DQM successively minimizes approximations of the cost, it converges to the optimal arguments at a linear rate which is identical to the convergence rate of DADMM. Further, we show that as time passes the coefficient of linear convergence for DQM approaches the one for DADMM. Numerical results demonstrate the effectiveness of DQM.

preprint2015arXiv

DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers

This paper considers decentralized consensus optimization problems where nodes of a network have access to different summands of a global objective function. Nodes cooperate to minimize the global objective by exchanging information with neighbors only. A decentralized version of the alternating directions method of multipliers (DADMM) is a common method for solving this category of problems. DADMM exhibits linear convergence rate to the optimal objective but its implementation requires solving a convex optimization problem at each iteration. This can be computationally costly and may result in large overall convergence times. The decentralized quadratically approximated ADMM algorithm (DQM), which minimizes a quadratic approximation of the objective function that DADMM minimizes at each iteration, is proposed here. The consequent reduction in computational time is shown to have minimal effect on convergence properties. Convergence still proceeds at a linear rate with a guaranteed constant that is asymptotically equivalent to the DADMM linear convergence rate constant. Numerical results demonstrate advantages of DQM relative to DADMM and other alternatives in a logistic regression problem.

preprint2015arXiv

DSA: Decentralized Double Stochastic Averaging Gradient Algorithm

This paper considers convex 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.

preprint2015arXiv

Interior Point Method for Dynamic Constrained Optimization in Continuous Time

This paper considers a class of convex optimization problems where both, the objective function and the constraints, have a continuously varying dependence on time. Our goal is to develop an algorithm to track the optimal solution as it continuously changes over time inside or on the boundary of the dynamic feasible set. We develop an interior point method that asymptotically succeeds in tracking this optimal point in nonstationary settings. The method utilizes a time varying constraint slack and a prediction-correction structure that relies on time derivatives of functions and constraints and Newton steps in the spatial domain. Error free tracking is guaranteed under customary assumptions on the optimization problems and time differentiability of objective and constraints. The effectiveness of the method is illustrated in a problem that involves multiple agents tracking multiple targets.

preprint2015arXiv

Metrics in the Space of High Order Networks

This paper presents methods to compare high order networks, defined as weighted complete hypergraphs collecting relationship functions between elements of tuples. They can be considered as generalizations of conventional networks where only relationship functions between pairs are defined. Important properties between relationships of tuples of different lengths are established, particularly when relationships encode dissimilarities or proximities between nodes. Two families of distances are then introduced in the space of high order networks. The distances measure differences between networks. We prove that they are valid metrics in the spaces of high order dissimilarity and 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.

preprint2015arXiv

Network Newton-Part I: Algorithm and Convergence

We study the problem of minimizing a sum of convex objective functions where the components of the objective are available at different nodes of a network and nodes are allowed to only communicate with their neighbors. The use of distributed gradient methods is a common approach to solve this problem. Their popularity notwithstanding, these methods exhibit slow convergence and a consequent large number of communications between nodes to approach the optimal argument because they rely on first order information only. This paper proposes the network Newton (NN) method as a distributed algorithm that incorporates second order information. This is done via distributed implementation of approximations of a suitably chosen Newton step. The approximations are obtained by truncation of the Newton step's Taylor expansion. This leads to a family of methods defined by the number $K$ of Taylor series terms kept in the approximation. When keeping $K$ terms of the Taylor series, the method is called NN-$K$ and can be implemented through the aggregation of information in $K$-hop neighborhoods. Convergence to a point close to the optimal argument at a rate that is at least linear is proven and the existence of a tradeoff between convergence time and the distance to the optimal argument is shown. Convergence rate, several practical implementation matters, and numerical analyses are presented in a companion paper [3].

preprint2015arXiv

Network Newton-Part II: Convergence Rate and Implementation

The use of network Newton methods for the decentralized optimization of a sum cost distributed through agents of a network is considered. Network Newton methods reinterpret distributed gradient descent as a penalty method, observe that the corresponding Hessian is sparse, and approximate the Newton step by truncating a Taylor expansion of the inverse Hessian. Truncating the series at $K$ terms yields the NN-$K$ that requires aggregating information from $K$ hops away. Network Newton is introduced and shown to converge to the solution of the penalized objective function at a rate that is at least linear in a companion paper [3]. The contributions of this work are: (i) To complement the convergence analysis by studying the methods' rate of convergence. (ii) To introduce adaptive formulations that converge to the optimal argument of the original objective. (iii) To perform numerical evaluations of NN-$K$ methods. The convergence analysis relates the behavior of NN-$K$ with the behavior of (regular) Newton's method and shows that the method goes through a quadratic convergence phase in a specific interval. The length of this quadratic phase grows with $K$ and can be made arbitrarily large. The numerical experiments corroborate reductions in the number of iterations and the communication cost that are necessary to achieve convergence relative to distributed gradient descent.

preprint2015arXiv

Reconstruction of Graph Signals through Percolation from Seeding Nodes

New schemes to recover signals defined in the nodes of a graph are proposed. Our focus is on reconstructing bandlimited graph signals, which are signals that admit a sparse representation in a frequency domain related to the structure of the graph. Most existing formulations focus on estimating an unknown graph signal by observing its value on a subset of nodes. By contrast, in this paper, we study the problem of reconstructing a known graph signal using as input a graph signal that is non-zero only for a small subset of nodes (seeding nodes). The sparse signal is then percolated (interpolated) across the graph using a graph filter. Graph filters are a generalization of classical time-invariant systems and represent linear transformations that can be implemented distributedly across the nodes of the graph. Three setups are investigated. In the first one, a single simultaneous injection takes place on several nodes in the graph. In the second one, successive value injections take place on a single node. The third one is a generalization where multiple nodes inject multiple signal values. For noiseless settings, conditions under which perfect reconstruction is feasible are given, and the corresponding schemes to recover the desired signal are specified. Scenarios leading to imperfect reconstruction, either due to insufficient or noisy signal value injections, are also analyzed. Moreover, connections with classical interpolation in the time domain are discussed. The last part of the paper presents numerical experiments that illustrate the results developed through synthetic graph signals and two real-world signal reconstruction problems: influencing opinions in a social network and inducing a desired brain state in humans.

preprint2015arXiv

Sampling of graph signals with successive local aggregations

A new scheme to sample signals defined in the nodes of a graph is proposed. The underlying assumption is that such signals admit a sparse representation in a frequency domain related to the structure of the graph, which is captured by the so-called graph-shift operator. Most of the works that have looked at this problem have focused on using the value of the signal observed at a subset of nodes to recover the signal in the entire graph. Differently, the sampling scheme proposed here uses as input observations taken at a single node. The observations correspond to sequential applications of the graph-shift operator, which are linear combinations of the information gathered by the neighbors of the node. When the graph corresponds to a directed cycle (which is the support of time-varying signals), our method is equivalent to the classical sampling in the time domain. When the graph is more general, we show that the Vandermonde structure of the sampling matrix, which is critical to guarantee recovery when sampling time-varying signals, is preserved. Sampling and interpolation are analyzed first in the absence of noise and then noise is considered. We then study the recovery of the sampled signal when the specific set of frequencies that is active is not known. Moreover, we present a more general sampling scheme, under which, either our aggregation approach or the alternative approach of sampling a graph signal by observing the value of the signal at a subset of nodes can be both viewed as particular cases. The last part of the paper presents numerical experiments that illustrate the results developed through both synthetic graph signals and a real-world graph of the economy of the United States.

preprint2014arXiv

A Quasi-Newton Method for Large Scale Support Vector Machines

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.

preprint2014arXiv

Authorship Attribution through Function Word Adjacency Networks

A method for authorship attribution based on function word adjacency networks (WANs) is introduced. Function words are parts of speech that express grammatical relationships between other words but do not carry lexical meaning on their own. In the WANs in this paper, nodes are function words and directed edges stand in for the likelihood of finding the sink word in the ordered vicinity of the source word. WANs of different authors can be interpreted as transition probabilities of a Markov chain and are therefore compared in terms of their relative entropies. Optimal selection of WAN parameters is studied and attribution accuracy is benchmarked across a diverse pool of authors and varying text lengths. This analysis shows that, since function words are independent of content, their use tends to be specific to an author and that the relational data captured by function WANs is a good summary of stylometric fingerprints. Attribution accuracy is observed to exceed the one achieved by methods that rely on word frequencies alone. Further combining WANs with methods that rely on word frequencies alone, results in larger attribution accuracy, indicating that both sources of information encode different aspects of authorial styles.

preprint2014arXiv

Axiomatic Construction of Hierarchical Clustering in Asymmetric Networks

This paper considers networks where relationships between nodes are represented by directed dissimilarities. The goal is to study methods for the determination of hierarchical clusters, i.e., a family of nested partitions indexed by a connectivity parameter, induced by the given dissimilarity structures. Our construction of hierarchical clustering methods is based on defining admissible methods to be those methods that abide by the axioms of value - nodes in a network with two nodes are clustered together at the maximum of the two dissimilarities between them - and transformation - when dissimilarities are reduced, the network may become more clustered but not less. Several admissible methods are constructed and two particular methods, termed reciprocal and nonreciprocal clustering, are shown to provide upper and lower bounds in the space of admissible methods. Alternative clustering methodologies and axioms are further considered. Allowing the outcome of hierarchical clustering to be asymmetric, so that it matches the asymmetry of the original data, leads to the inception of quasi-clustering methods. The existence of a unique quasi-clustering method is shown. Allowing clustering in a two-node network to proceed at the minimum of the two dissimilarities generates an alternative axiomatic construction. There is a unique clustering method in this case too. The paper also develops algorithms for the computation of hierarchical clusters using matrix powers on a min-max dioid algebra and studies the stability of the methods proposed. We proved that most of the methods introduced in this paper are such that similar networks yield similar hierarchical clustering results. Algorithms are exemplified through their application to networks describing internal migration within states of the United States (U.S.) and the interrelation between sectors of the U.S. economy.

preprint2014arXiv

Diffusion and Superposition Distances for Signals Supported on Networks

We introduce the diffusion and superposition distances as two metrics to compare signals supported in the nodes of a network. Both metrics consider the given vectors as initial temperature distributions and diffuse heat trough the edges of the graph. The similarity between the given vectors is determined by the similarity of the respective diffusion profiles. The superposition distance computes the instantaneous difference between the diffused signals and integrates the difference over time. The diffusion distance determines a distance between the integrals of the diffused signals. We prove that both distances define valid metrics and that they are stable to perturbations in the underlying network. We utilize numerical experiments to illustrate their utility in classifying signals in a synthetic network as well as in classifying ovarian cancer histologies using gene mutation profiles of different patients. We also reinterpret diffusion as a transformation of interrelated feature spaces and use it as preprocessing tool for learning. We use diffusion to increase the accuracy of handwritten digit classification.

preprint2014arXiv

Global Convergence of Online Limited Memory BFGS

Global convergence of an online (stochastic) limited memory version of the Broyden-Fletcher- Goldfarb-Shanno (BFGS) quasi-Newton method for solving optimization problems with stochastic objectives that arise in large scale machine learning is established. Lower and upper bounds on the Hessian eigenvalues of the sample functions are shown to suffice to guarantee that the curvature approximation matrices have bounded determinants and traces, which, in turn, permits establishing convergence to optimal arguments with probability 1. Numerical experiments on support vector machines with synthetic data showcase reductions in convergence time relative to stochastic gradient descent algorithms as well as reductions in storage and computation relative to other online quasi-Newton methods. Experimental evaluation on a search engine advertising problem corroborates that these advantages also manifest in practical applications.

preprint2014arXiv

Hierarchical Quasi-Clustering Methods for Asymmetric Networks

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.

preprint2014arXiv

Network Newton

We consider minimization of a sum of convex objective functions where the components of the objective are available at different nodes of a network and nodes are allowed to only communicate with their neighbors. The use of distributed subgradient or gradient methods is widespread but they often suffer from slow convergence since they rely on first order information, which leads to a large number of local communications between nodes in the network. In this paper we propose the Network Newton (NN) method as a distributed algorithm that incorporates second order information via distributed evaluation of approximations to Newton steps. We also introduce adaptive (A)NN in order to establish exact convergence. Numerical analyses show significant improvement in both convergence time and number of communications for NN relative to existing (first order) alternatives.

preprint2014arXiv

RES: Regularized Stochastic BFGS Algorithm

RES, a regularized stochastic version of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi-Newton method is proposed to solve convex optimization problems with stochastic objectives. The use of stochastic gradient descent algorithms is widespread, but the number of iterations required to approximate optimal arguments can be prohibitive in high dimensional problems. Application of second order methods, on the other hand, is impracticable because computation of objective function Hessian inverses incurs excessive computational cost. BFGS modifies gradient descent by introducing a Hessian approximation matrix computed from finite gradient differences. RES utilizes stochastic gradients in lieu of deterministic gradients for both, the determination of descent directions and the approximation of the objective function's curvature. Since stochastic gradients can be computed at manageable computational cost RES is realizable and retains the convergence rate advantages of its deterministic counterparts. Convergence results show that lower and upper bounds on the Hessian egeinvalues of the sample functions are sufficient to guarantee convergence to optimal arguments. Numerical experiments showcase reductions in convergence time relative to stochastic gradient descent algorithms and non-regularized stochastic versions of BFGS. An application of RES to the implementation of support vector machines is developed.

preprint2014arXiv

Stability and Continuity of Centrality Measures in Weighted Graphs

This paper presents a formal definition of stability for node centrality measures in weighted graphs. It is shown that the commonly used measures of degree, closeness and eigenvector centrality are stable whereas betweenness centrality is not. An alternative definition of the latter that preserves the same centrality notion while satisfying the stability criteria is introduced. Continuity is presented as a less stringent alternative to stability. Betweenness centrality is shown to be not only unstable but discontinuous. Numerical experiments in synthetic random networks and real-world data show that, in practice, stability and continuity imply different levels of robustness in the presence of noisy data. In particular, the stable betweenness centrality is shown to exhibit resilience against noise that is absent in the discontinuous and unstable standard betweenness centrality, while preserving a similar notion of centrality.

preprint2013arXiv

Accelerated Backpressure Algorithm

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.

preprint2013arXiv

Bayesian Quadratic Network Game Filters

A repeated network game where agents have quadratic utilities that depend on information externalities -- an unknown underlying state -- as well as payoff externalities -- the actions of all other agents in the network -- 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 Cournot market competition game and a coordination game to implement navigation of an autonomous team.

preprint2012arXiv

A Distributed Line Search for Network Optimization

Dual descent methods are used to solve network optimization problems because descent directions can be computed in a distributed manner using information available either locally or at neighboring nodes. However, choosing a stepsize in the descent direction remains a challenge because its computation requires global information. This work presents an algorithm based on a local version of the Armijo rule that allows for the computation of a stepsize using only local and neighborhood information. We show that when our distributed line search algorithm is applied with a descent direction computed according to the Accelerated Dual Descent method \cite{acc11}, key properties of standard backtracking line search using the Armijo rule are recovered. We use simulations to demonstrate that our algorithm is a practical substitute for its centralized counterpart.