Search

This paper presents a time-constrained model predictive control strategy for the six degree-of-freedom autonomous rendezvous, proximity, operations and docking problem between a controllable "deputy" satellite and an uncontrolled "chief" satellite. The objective is to achieve a docking configuration defined by both the translational and attitudinal states of the deputy relative to the chief, whose dynamics are respectively governed by both the Clohessy-Wiltshire equations and Euler's second law of motion. The proposed control strategy explicitly addresses computational time constraints that are common to state-of-the-art space vehicles. Thus, a time-constrained model predictive control strategy is implemented on a space-grade processor. Although suboptimal with regards to energy consumption when compared to conventional optimal RPO trajectories, it is empirically demonstrated via numerical simulations that the deputy spacecraft still achieves a successful docking configuration while subject to computational time constraints., Comment: arXiv admin note: text overlap with arXiv:2211.11653

The study of spreading processes often analyzes networks at different resolutions, e.g., at the level of individuals or countries, but it is not always clear how properties at one resolution can carry over to another. Accordingly, in this work we use dissipativity theory from control system analysis to characterize composite spreading networks that are comprised by many interacting subnetworks. We first develop a method to represent spreading networks that have inputs and outputs. Then we define a composition operation for composing multiple spreading networks into a larger composite spreading network. Next, we develop storage and supply rate functions that can be used to demonstrate that spreading dynamics are dissipative. We then derive conditions under which a composite spreading network will converge to a disease-free equilibrium as long as its constituent spreading networks are dissipative with respect to those storage and supply rate functions. To illustrate these results, we use simulations of an influenza outbreak in a primary school, and we show that an outbreak can be prevented by decreasing the average interaction time between any pair of classes to less than 79% of the original interaction time.

We present a distributed algorithm to track the fixed points of time-varying quadratic programs when agents can (i) sample their objective function asynchronously, (ii) compute new iterates asynchronously, and (iii) communicate asynchronously. We show that even for a time-varying strongly convex quadratic program, asynchronous sampling of objectives can cause agents to minimize a certain form of nonconvex "aggregate" objective function. Then, we show that by minimizing the aggregate objective, agents still track the solution of the original quadratic program to within an error ball dependent upon (i) agents' tracking error when solving the aggregate problem, and (ii) the time variation of the original quadratic objective. Lastly, we show that this work generalizes existing work, in the sense that synchronizing the agents' behaviors recovers existing convergence results (up to constants). Simulations show the robustness of our algorithm to asynchrony.

In this paper we solve mixed-integer linear programs (MILPs) via distributed asynchronous saddle point computation. This work is motivated by the MILPs being able to model problems in multi-agent autonomy, such as task assignment problems and trajectory planning with collision avoidance constraints in multi-robot systems. To solve a MILP, we relax it with a linear program approximation. We first show that if the linear program relaxation satisfies Slater's condition, then relaxing the problem, solving it, and rounding the relaxed solution produces a point that is guaranteed to satisfy the constraints of the original MILP. Next, we form a Lagrangian saddle point problem that is equivalent to the linear program relaxation, and then we regularize the Lagrangian in both the primal and dual spaces. Doing so gives a regularized Lagrangian that is strongly convex-strongly concave. We then develop a parallelized algorithm to compute saddle points of the regularized Lagrangian, and we show that it is tolerant to asynchrony in the computations and communications of primal and dual variables. Suboptimality bounds and convergence rates are presented for convergence to a saddle point. The suboptimality bound accounts for (i) the error induced by regularizing the Lagrangian and (ii) the suboptimality gap between the solution to the original MILP and the solution to its relaxed form. Simulation results illustrate these theoretical developments in practice, and show that relaxation and regularization combined typically have only a mild impact on the suboptimality of the solution obtained., Comment: 22 pages, 4 figures. arXiv admin note: text overlap with arXiv:2211.11842

Convex programming with linear constraints plays an important role in the operation of a number of everyday systems. However, absent any additional protections, revealing or acting on the solutions to such problems may reveal information about their constraints, which can be sensitive. Therefore, in this paper, we introduce a method for solving convex programs while keeping linear constraints private. First, we prove that this method is differentially private and always generates a feasible optimization problem (i.e., one whose solution exists). Then we show that the solution to the privatized problem also satisfies the original, non-private constraints. Next, we bound the expected loss in performance from privacy, which is measured by comparing the cost with privacy to that without privacy. Simulation results apply this framework to constrained policy synthesis in a Markov decision process, and they show that a typical privacy implementation induces only an approximately $9\%$ loss in solution quality., Comment: 2 figures, 6 pages

We present a totally asynchronous algorithm for convex optimization that is based on a novel generalization of Nesterov's accelerated gradient method. This algorithm is developed for fast convergence under "total asynchrony," i.e., allowing arbitrarily long delays between agents' computations and communications without assuming any form of delay bound. These conditions may arise, for example, due to jamming by adversaries. Our framework is block-based, in the sense that each agent is only responsible for computing updates to (and communicating the values of) a small subset of the network-level decision variables. In our main result, we present bounds on the algorithm's parameters that guarantee linear convergence to an optimizer. Then, we quantify the relationship between (i) the total number of computations and communications executed by the agents and (ii) the agents' collective distance to an optimum. Numerical simulations show that this algorithm requires 28% fewer iterations than the heavy ball algorithm and 61% fewer iterations than gradient descent under total asynchrony., Comment: 11 pages, 1 figure

It is common in pose graph optimization (PGO) algorithms to assume that noise in the translations and rotations of relative pose measurements is uncorrelated. However, existing work shows that in practice these measurements can be highly correlated, which leads to degradation in the accuracy of PGO solutions that rely on this assumption. Therefore, in this paper we develop a novel algorithm derived from a realistic, correlated model of relative pose uncertainty, and we quantify the resulting improvement in the accuracy of the solutions we obtain relative to state-of-the-art PGO algorithms. Our approach utilizes Riemannian optimization on the planar unit dual quaternion (PUDQ) manifold, and we prove that it converges to first-order stationary points of a Lie-theoretic maximum likelihood objective. Then we show experimentally that, compared to state-of-the-art PGO algorithms, this algorithm produces estimation errors that are lower by 10% to 25% across several orders of magnitude of noise levels and graph sizes., Comment: 61 pages

Optimization decomposition methods are a fundamental tool to develop distributed solution algorithms for large scale optimization problems arising in fields such as machine learning and optimal control. In this paper, we present an algebraic framework for hierarchically composing optimization problems defined on hypergraphs and automatically generating distributed solution algorithms that respect the given hierarchical structure. The central abstractions of our framework are operads, operad algebras, and algebra morphisms, which formalize notions of syntax, semantics, and structure preserving semantic transformations respectively. These abstractions allow us to formally relate composite optimization problems to the distributed algorithms that solve them. Specifically, we show that certain classes of optimization problems form operad algebras, and a collection of first-order solution methods, namely gradient descent, Uzawa's algorithm (also called gradient ascent-descent), and their subgradient variants, yield algebra morphisms from these problem algebras to algebras of dynamical systems. Primal and dual decomposition methods are then recovered by applying these morphisms to certain classes of composite problems. Using this framework, we also derive a novel sufficient condition for when a problem defined by compositional data is solvable by a decomposition method. We show that the minimum cost network flow problem satisfies this condition, thereby allowing us to automatically derive a hierarchical dual decomposition algorithm for finding minimum cost flows on composite flow networks. We implement our operads, algebras, and algebra morphisms in a Julia package called AlgebraicOptimization.jl and use our implementation to empirically demonstrate that hierarchical dual decomposition outperforms standard dual decomposition on classes of flow networks with hierarchical structure.

Modeling epidemic spread is critical for informing policy decisions aimed at mitigation. Accordingly, in this work we present a new data-driven method based on Gaussian process regression (GPR) to model epidemic spread through the difference on the logarithmic scale of the infected cases. We bound the variance of the predictions made by GPR, which quantifies the impact of epidemic data on the proposed model. Next, we derive a high-probability error bound on the prediction error in terms of the distance between the training points and a testing point, the posterior variance, and the level of change in the spreading process, and we assess how the characteristics of the epidemic spread and infection data influence this error bound. We present examples that use GPR to model and predict epidemic spread by using real-world infection data gathered in the UK during the COVID-19 epidemic. These examples illustrate that, under typical conditions, the prediction for the next twenty days has 94.29% of the noisy data located within the 95% confidence interval, validating these predictions. We further compare the modeling and prediction results with other methods, such as polynomial regression, k-nearest neighbors (KNN) regression, and neural networks, to demonstrate the benefits of leveraging GPR in disease spread modeling., Comment: The code for the analyses is available at https://github.com/baikeshe/GPR_Epi_Modeling

In this article, we present an algorithm that drives the outputs of a network of agents to jointly track the solutions of time-varying optimization problems in a way that is robust to asynchrony in the agents' operations. We consider three operations that can be asynchronous: (1) computations of control inputs, (2) measurements of network outputs, and (3) communications of agents' inputs and outputs. We first show that our algorithm converges to the solution of a time-invariant feedback optimization problem in linear time. Next, we show that our algorithm drives outputs to track the solution of time-varying feedback optimization problems within a bounded error dependent upon the movement of the minimizers and degree of asynchrony in a way that we make precise. These convergence results are extended to quantify agents' asymptotic behavior as the length of their time horizon approaches infinity. Then, to ensure satisfactory network performance, we specify the timing of agents' operations relative to changes in the objective function that ensure a desired error bound. Numerical experiments confirm these developments and show the success of our distributed feedback optimization algorithm under asynchrony.

The basic reproduction number of a networked epidemic model, denoted $R_0$, can be computed from a network's topology to quantify epidemic spread. However, disclosure of $R_0$ risks revealing sensitive information about the underlying network, such as an individual's relationships within a social network. Therefore, we propose a framework to compute and release $R_0$ in a differentially private way. First, we provide a new result that shows how $R_0$ can be used to bound the level of penetration of an epidemic within a single community as a motivation for the need of privacy, which may also be of independent interest. We next develop a privacy mechanism to formally safeguard the edge weights in the underlying network when computing $R_0$. Then we formalize tradeoffs between the level of privacy and the accuracy of values of the privatized $R_0$. To show the utility of the private $R_0$ in practice, we use it to bound this level of penetration under privacy, and concentration bounds on these analyses show they remain accurate with privacy implemented. We apply our results to real travel data gathered during the spread of COVID-19, and we show that, under real-world conditions, we can compute $R_0$ in a differentially private way while incurring errors as low as $7.6\%$ on average., Comment: 8 pages, 3 figures

Markov decision processes often seek to maximize a reward function, but onlookers may infer reward functions by observing the states and actions of such systems, revealing sensitive information. Therefore, in this paper we introduce and compare two methods for privatizing reward functions in policy synthesis for multi-agent Markov decision processes, which generalize Markov decision processes. Reward functions are privatized using differential privacy, a statistical framework for protecting sensitive data. The methods we develop perturb either (1) each agent's individual reward function or (2) the joint reward function shared by all agents. We show that approach (1) provides better performance. We then develop a polynomial-time algorithm for the numerical computation of the performance loss due to privacy on a case-by-case basis. Next, using approach (1), we develop guidelines for selecting reward function values to preserve ``goal" and ``avoid" states while still remaining private, and we quantify the increase in computational complexity needed to compute policies from privatized rewards. Numerical simulations are performed on three classes of systems and they reveal a surprising compatibility with privacy: using reasonably strong privacy ($\epsilon =1.3$) on average induces as little as a~$5\%$ decrease in total accumulated reward and a $0.016\%$ increase in computation time., Comment: 16 Pages, 11 figures

In cooperative multi-agent reinforcement learning (Co-MARL), a team of agents must jointly optimize the team's long-term rewards to learn a designated task. Optimizing rewards as a team often requires inter-agent communication and data sharing, leading to potential privacy implications. We assume privacy considerations prohibit the agents from sharing their environment interaction data. Accordingly, we propose Privacy-Engineered Value Decomposition Networks (PE-VDN), a Co-MARL algorithm that models multi-agent coordination while provably safeguarding the confidentiality of the agents' environment interaction data. We integrate three privacy-engineering techniques to redesign the data flows of the VDN algorithm, an existing Co-MARL algorithm that consolidates the agents' environment interaction data to train a central controller that models multi-agent coordination, and develop PE-VDN. In the first technique, we design a distributed computation scheme that eliminates Vanilla VDN's dependency on sharing environment interaction data. Then, we utilize a privacy-preserving multi-party computation protocol to guarantee that the data flows of the distributed computation scheme do not pose new privacy risks. Finally, we enforce differential privacy to preempt inference threats against the agents' training data, past environment interactions, when they take actions based on their neural network predictions. We implement PE-VDN in StarCraft Multi-Agent Competition (SMAC) and show that it achieves 80% of Vanilla VDN's win rate while maintaining differential privacy levels that provide meaningful privacy guarantees. The results demonstrate that PE-VDN can safeguard the confidentiality of agents' environment interaction data without sacrificing multi-agent coordination., Comment: Paper accepted at 62nd IEEE Conference on Decision and Control

Out-of-distribution (OOD) generalization poses a serious challenge for modern deep learning (DL). OOD data consists of test data that is significantly different from the model's training data. DL models that perform well on in-domain test data could struggle on OOD data. Overcoming this discrepancy is essential to the reliable deployment of DL. Proper model calibration decreases the number of spurious connections that are made between model features and class outputs. Hence, calibrated DL can improve OOD generalization by only learning features that are truly indicative of the respective classes. Previous work proposed domain-aware model calibration (DOMINO) to improve DL calibration, but it lacks designs for model generalizability to OOD data. In this work, we propose DOMINO++, a dual-guidance and dynamic domain-aware loss regularization focused on OOD generalizability. DOMINO++ integrates expert-guided and data-guided knowledge in its regularization. Unlike DOMINO which imposed a fixed scaling and regularization rate, DOMINO++ designs a dynamic scaling factor and an adaptive regularization rate. Comprehensive evaluations compare DOMINO++ with DOMINO and the baseline model for head tissue segmentation from magnetic resonance images (MRIs) on OOD data. The OOD data consists of synthetic noisy and rotated datasets, as well as real data using a different MRI scanner from a separate site. DOMINO++'s superior performance demonstrates its potential to improve the trustworthy deployment of DL on real clinical data., Comment: 12 pages, 5 figures, 5 tables, Accepted by the International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI) 2023

Model predictive control (MPC) is an optimal control technique which involves solving a sequence of constrained optimization problems across a given time horizon. In this paper, we introduce a category theoretic framework for constructing complex MPC problem formulations by composing subproblems. Specifically, we construct a monoidal category - called Para(Conv) - whose objects are Euclidean spaces and whose morphisms represent constrained convex optimization problems. We then show that the multistage structure of typical MPC problems arises from sequential composition in Para(Conv), while parallel composition can be used to model constraints across multiple stages of the prediction horizon. This framework comes equipped with a rigorous, diagrammatic syntax, allowing for easy visualization and modification of complex problems. Finally, we show how this framework allows a simple software realization in the Julia programming language by integrating with existing mathematical programming libraries to provide high-level, graphical abstractions for MPC., Comment: To appear in the proceedings of the 2024 American Control Conference (ACC)

Composing systems is a fundamental concept in modern control systems, yet it remains challenging to formally analyze how controllers designed for individual subsystems can differ from controllers designed for the composition of those subsystems. To address this challenge, we propose a novel approach to composing control systems based on resource sharing machines, a concept from applied category theory. We use resource sharing machines to investigate the differences between (i) the linear-quadratic regulator (LQR) designed directly for a composite system and (ii) the LQR that is attained through the composition of LQRs designed for each subsystem. We first establish novel formalisms to compose LQR control designs using resource sharing machines. Then we develop new sufficient conditions to guarantee that the LQR designed for a composite system is equal to the LQR attained through composition of LQRs for its subsystems. In addition, we reduce the developed condition to that of checking the controllability and observability of a certain linear, time-invariant system, which provides a simple, computationally efficient procedure for evaluating the equivalence of controllers for composed systems.

This paper considers the quickest search problem to identify anomalies among large numbers of data streams. These streams can model, for example, disjoint regions monitored by a mobile robot. A particular challenge is a version of the problem in which the experimenter must suffer a cost each time the data stream being sampled changes, such as the time the robot must spend moving between regions. In this paper, we propose an algorithm which accounts for switching costs by varying a confidence threshold that governs when the algorithm switches to a new data stream. Our main contributions are easily computable approximations for both the optimal value of this threshold and the optimal value of the parameter that determines when a stream must be re-sampled. Further, we empirically show (i) a uniform improvement for switching costs of interest and (ii) roughly equivalent performance for small switching costs when comparing to the closest available algorithm., Comment: 6 pages, 4 figures

Deep learning has achieved the state-of-the-art performance across medical imaging tasks; however, model calibration is often not considered. Uncalibrated models are potentially dangerous in high-risk applications since the user does not know when they will fail. Therefore, this paper proposes a novel domain-aware loss function to calibrate deep learning models. The proposed loss function applies a class-wise penalty based on the similarity between classes within a given target domain. Thus, the approach improves the calibration while also ensuring that the model makes less risky errors even when incorrect. The code for this software is available at https://github.com/lab-smile/DOMINO., Comment: 7 pages, 1 figure, 1 table, accepted by the Software Impacts journal

Privacy-aware multiagent systems must protect agents' sensitive data while simultaneously ensuring that agents accomplish their shared objectives. Towards this goal, we propose a framework to privatize inter-agent communications in cooperative multiagent decision-making problems. We study sequential decision-making problems formulated as cooperative Markov games with reach-avoid objectives. We apply a differential privacy mechanism to privatize agents' communicated symbolic state trajectories, and then we analyze tradeoffs between the strength of privacy and the team's performance. For a given level of privacy, this tradeoff is shown to depend critically upon the total correlation among agents' state-action processes. We synthesize policies that are robust to privacy by reducing the value of the total correlation. Numerical experiments demonstrate that the team's performance under these policies decreases by only 3 percent when comparing private versus non-private implementations of communication. By contrast, the team's performance decreases by roughly 86 percent when using baseline policies that ignore total correlation and only optimize team performance.

Reproduction numbers are widely used for the estimation and prediction of epidemic spreading processes over networks. However, reproduction numbers do not enable estimation and prediction in individual communities within networks, and they can be difficult to compute due to the aggregation of infection data that is required to do so. Therefore, in this work we propose a novel concept of distributed reproduction numbers to capture the spreading behaviors of each entity in the network, and we show how to compute them using certain parameters in networked SIS and SIR epidemic models. We use distributed reproduction numbers to derive new conditions under which an outbreak can occur. These conditions are then used to derive new conditions for the existence, uniqueness, and stability of equilibrium states. Finally, in simulation we use synthetic infection data to illustrate how distributed reproduction numbers provide more fine-grained analyses of networked spreading processes than ordinary reproduction numbers.

Control barrier functions are a popular method of ensuring system safety, and these functions can be used to enforce invariance of a set under the dynamics of a system. A control barrier function must have certain properties, and one must both formulate a candidate control barrier function and verify that it does indeed satisfy the required properties. Targeting the latter problem, this paper presents a method of verifying any finite number of candidate control barrier functions with linear programming. We first apply techniques from real algebraic geometry to formulate verification problem statements that are solvable numerically. Typically, semidefinite programming is used to verify candidate control barrier functions, but this does not always scale well. Therefore, we next apply a method of inner-approximating the set of sums of squares polynomials that significantly reduces the computational complexity of these verification problems by transcribing them to linear programs. We give explicit forms for the resulting linear programs, and simulation results for a satellite inspection problem show that the computation time needed for verification can be reduced by more than 95%., Comment: 8 pages, 1 figure

The Gaussian mechanism is one differential privacy mechanism commonly used to protect numerical data. However, it may be ill-suited to some applications because it has unbounded support and thus can produce invalid numerical answers to queries, such as negative ages or human heights in the tens of meters. One can project such private values onto valid ranges of data, though such projections lead to the accumulation of private query responses at the boundaries of such ranges, thereby harming accuracy. Motivated by the need for both privacy and accuracy over bounded domains, we present a bounded Gaussian mechanism for differential privacy, which has support only on a given region. We present both univariate and multivariate versions of this mechanism and illustrate a significant reduction in variance relative to comparable existing work., Comment: 27 pages, submitted to Journal of Privacy and Confidentiality

This paper develops a framework for privatizing the spectrum of the graph Laplacian of an undirected graph using differential privacy. We consider two privacy formulations. The first obfuscates the presence of edges in the graph and the second obfuscates the presence of nodes. We compare these two privacy formulations and show that the privacy formulation that considers edges is better suited to most engineering applications. We use the bounded Laplace mechanism to provide differential privacy to the eigenvalues of a graph Laplacian, and we pay special attention to the algebraic connectivity, which is the Laplacian's second smallest eigenvalue. Analytical bounds are presented on the the accuracy of the mechanisms and on certain graph properties computed with private spectra. A suite of numerical examples confirms the accuracy of private spectra in practice., Comment: arXiv admin note: text overlap with arXiv:2104.00654

We solve large-scale mixed-integer linear programs (MILPs) via distributed asynchronous saddle point computation. This is motivated by the MILPs being able to model problems in multi-agent autonomy, e.g., task assignment problems and trajectory planning with collision avoidance constraints in multi-robot systems. To solve a MILP, we relax it with a nonlinear program approximation whose accuracy tightens as the number of agents increases relative to the number of coupled constraints. Next, we form an equivalent Lagrangian saddle point problem, and then regularize the Lagrangian in both the primal and dual spaces to create a regularized Lagrangian that is strongly-convex-strongly-concave. We then develop a parallelized algorithm to compute saddle points of the regularized Lagrangian. This algorithm partitions problems into blocks, which are either scalars or sub-vectors of the primal or dual decision variables, and it is shown to tolerate asynchrony in the computations and communications of primal and dual variables. Suboptimality bounds and convergence rates are presented for convergence to a saddle point. The suboptimality bound includes (i) the regularization error induced by regularizing the Lagrangian and (ii) the suboptimality gap between solutions to the original MILP and its relaxed form. Simulation results illustrate these theoretical developments in practice, and show that relaxation and regularization together have only a mild impact on the quality of solution obtained., Comment: 14 pages, 2 figures

This paper presents a time-constrained model predictive control strategy for the 6 degree-of-freedom (6DOF) autonomous rendezvous and docking problem between a controllable "deputy" spacecraft and an uncontrollable "chief" spacecraft. The control strategy accounts for computational time constraints due to limited onboard processing speed. The translational dynamics model is derived from the Clohessy-Wiltshire equations and the angular dynamics are modeled on gas jet actuation about the deputy's center of mass. Simulation results are shown to achieve the docking configuration under computational time constraints by limiting the number of allowed algorithm iterations when computing each input. Specifically, we show that upwards of 90% of computations can be eliminated from a model predictive control implementation without significantly harming control performance.

Model calibration measures the agreement between the predicted probability estimates and the true correctness likelihood. Proper model calibration is vital for high-risk applications. Unfortunately, modern deep neural networks are poorly calibrated, compromising trustworthiness and reliability. Medical image segmentation particularly suffers from this due to the natural uncertainty of tissue boundaries. This is exasperated by their loss functions, which favor overconfidence in the majority classes. We address these challenges with DOMINO, a domain-aware model calibration method that leverages the semantic confusability and hierarchical similarity between class labels. Our experiments demonstrate that our DOMINO-calibrated deep neural networks outperform non-calibrated models and state-of-the-art morphometric methods in head image segmentation. Our results show that our method can consistently achieve better calibration, higher accuracy, and faster inference times than these methods, especially on rarer classes. This performance is attributed to our domain-aware regularization to inform semantic model calibration. These findings show the importance of semantic ties between class labels in building confidence in deep learning models. The framework has the potential to improve the trustworthiness and reliability of generic medical image segmentation models. The code for this article is available at: https://github.com/lab-smile/DOMINO., Comment: 10 pages, 6 figures, 3 tables. Accepted by International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI) 2022 Oral Talk

As multi-agent systems proliferate, there is increasing need for coordination protocols that protect agents' sensitive information while still allowing them to collaborate. Often, a network system and controller are first designed and implemented, and then privacy is only incorporated after that. However, the absence of privacy from the design process can make it difficult to implement without significantly harming system performance. To help address this need, this paper presents a co-design framework for multi-agent networks and private controllers that we apply to the problem of private formation control. Agents' state trajectories are protected using differential privacy, which is a statistical notion of privacy that protects data by adding noise to it. Privacy noise alters the performance of the network, which we quantify by computing a bound for the steady-state error for private formations. Then, we analyze tradeoffs between privacy level, system performance, and connectedness of the network's communication topology. These trade-offs are used to formulate a co-design optimization framework to design the optimal communication topology alongside the optimal privacy parameters for a network running differentially private formation control. Simulation results illustrate the scalability of our proposed privacy/network co-design problem to large multi-agent networks, as well as the high quality of formations one can attain, even with privacy implemented., Comment: arXiv admin note: text overlap with arXiv:2004.02744

Satisfaction of the strict saddle property has become a standard assumption in non-convex optimization, and it ensures that many first-order optimization algorithms will almost always escape saddle points. However, functions exist in machine learning that do not satisfy this property, such as the loss function of a neural network with at least two hidden layers. First-order methods such as gradient descent may converge to non-strict saddle points of such functions, and there do not currently exist any first-order methods that reliably escape non-strict saddle points. To address this need, we demonstrate that regularizing a function with a linear term enforces the strict saddle property, and we provide justification for only regularizing locally, i.e., when the norm of the gradient falls below a certain threshold. We analyze bifurcations that may result from this form of regularization, and then we provide a selection rule for regularizers that depends only on the gradient of an objective function. This rule is shown to guarantee that gradient descent will escape the neighborhoods around a broad class of non-strict saddle points, and this behavior is demonstrated on numerical examples of non-strict saddle points common in the optimization literature., Comment: 8 pages, 6 figures

Distributed nonconvex optimization problems underlie many applications in learning and autonomy, and such problems commonly face asynchrony in agents' computations and communications. When delays in these operations are bounded, they are called partially asynchronous. In this paper, we present an uncoordinated stepsize selection rule for partially asynchronous block coordinate descent that only requires local information to implement, and it leads to faster convergence for a class of nonconvex problems than existing stepsize rules, which require global information in some form. The problems we consider satisfy the error bound condition, and the stepsize rule we present only requires each agent to know (i) a certain type of Lipschitz constant of its block of the gradient of the objective and (ii) the communication delays experienced between it and its neighbors. This formulation requires less information to be available to each agent than existing approaches, typically allows for agents to use much larger stepsizes, and alleviates the impact of stragglers while still guaranteeing convergence to a stationary point. Simulation results provide comparisons and validate the faster convergence attained by the stepsize rule we develop., Comment: 12 pages, 1 figure

Data-driven systems are gathering increasing amounts of data from users, and sensitive user data requires privacy protections. In some cases, the data gathered is non-numerical or symbolic, and conventional approaches to privacy, e.g., adding noise, do not apply, though such systems still require privacy protections. Accordingly, we present a novel differential privacy framework for protecting trajectories generated by symbolic systems. These trajectories can be represented as words or strings over a finite alphabet. We develop new differential privacy mechanisms that approximate a sensitive word using a random word that is likely to be near it. An offline mechanism is implemented efficiently using a Modified Hamming Distance Automaton to generate whole privatized output words over a finite time horizon. Then, an online mechanism is implemented by taking in a sensitive symbol and generating a randomized output symbol at each timestep. This work is extended to Markov chains to generate differentially private state sequences that a given Markov chain could have produced. Statistical accuracy bounds are developed to quantify the accuracy of these mechanisms, and numerical results validate the accuracy of these techniques for strings of English words., Comment: 16 pages, 9 figures, submitted to Automatica

This paper presents a decentralized algorithm for a team of agents to track time-varying fixed points that are the solutions to time-varying convex optimization problems. The algorithm is first-order, and it allows for total asynchrony in the communications and computations of all agents, i.e., all such operations can occur with arbitrary timing and arbitrary (finite) delays. Convergence rates are computed in terms of the communications and computations that agents execute, without specifying when they must occur. These rates apply to convergence to the minimum of each individual objective function, as well as agents' long-run behavior as their objective functions change. Then, to improve the usage of limited communication and computation resources, we optimize the timing of agents' operations relative to changes in their objective functions to minimize total fixed point tracking error over time. Simulation results are presented to illustrate these developments in practice and empirically assess their robustness to uncertainties in agents' update laws., Comment: 10 pages, 3 figures

We present a parallelized primal-dual algorithm for solving constrained convex optimization problems. The algorithm is "block-based," in that vectors of primal and dual variables are partitioned into blocks, each of which is updated only by a single processor. We consider four possible forms of asynchrony: in updates to primal variables, updates to dual variables, communications of primal variables, and communications of dual variables. We construct a family of explicit counterexamples to show the need to eliminate asynchronous communication of dual variables, though the other forms of asynchrony are permitted, all without requiring bounds on delays. A first-order primal-dual update law is developed and shown to be robust to asynchrony. We then derive convergence rates to a Lagrangian saddle point in terms of the operations agents execute, without specifying any timing or pattern with which they must be executed. These convergence rates include an "asynchrony penalty" that we quantify and present ways to mitigate. Numerical results illustrate these developments., Comment: arXiv admin note: text overlap with arXiv:2004.05142

We present a hybrid systems framework for multi-agent optimization in which agents execute computations in continuous time and communicate in discrete time. The optimization algorithm is a hybrid version of parallelized coordinate descent. Agents implement a sample-and-hold strategy in which gradients are computed at communication times and held constant during flows between communications. Completeness of maximal solutions under these hybrid dynamics is established. Under assumptions of smoothness and strong convexity, we show that this system exponentially converges to the minimizer of an objective function. Simulation results illustrate this convergence rate.

The joint optimisation of body-plan and control via evolutionary processes can be challenging in rich morphological spaces in which offspring can have body-plans that are very different from either of their parents. This causes a potential mismatch between the structure of an inherited controller and the new body. To address this, we propose a framework that combines an evolutionary algorithm to generate body-plans and a learning algorithm to optimise the parameters of a neural controller. The topology of this controller is created once the body-plan of each offspring body-plan is generated. The key novelty of the approach is to add an external archive for storing learned controllers that map to explicit `types' of robots (where this is defined with respect the features of the body-plan). By learning from a controller with an appropriate structure inherited from the archive, rather than from a randomly initialised one, we show that both the speed and magnitude of learning increases over time when compared to an approach that starts from scratch, using two tasks and three environments. The framework also provides new insights into the complex interactions between evolution and learning., Comment: 15 pages including 2 pages of supplementary materials, 16 figures, 1 table. Currently under review for the special issue of IEEE TCDS on Towards autonomous evolution, (re)production and learning in robotic eco-systems. https://www.york.ac.uk/robot-lab/are/ieee_special_issue_2020/

Graphs are the dominant formalism for modeling multi-agent systems. The algebraic connectivity of a graph is particularly important because it provides the convergence rates of consensus algorithms that underlie many multi-agent control and optimization techniques. However, sharing the value of algebraic connectivity can inadvertently reveal sensitive information about the topology of a graph, such as connections in social networks. Therefore, in this work we present a method to release a graph's algebraic connectivity under a graph-theoretic form of differential privacy, called edge differential privacy. Edge differential privacy obfuscates differences among graphs' edge sets and thus conceals the absence or presence of sensitive connections therein. We provide privacy with bounded Laplace noise, which improves accuracy relative to conventional unbounded noise. The private algebraic connectivity values are analytically shown to provide accurate estimates of consensus convergence rates, as well as accurate bounds on the diameter of a graph and the mean distance between its nodes. Simulation results confirm the utility of private algebraic connectivity in these contexts., Comment: 8 pages, 5 figures, submitted to 60th IEEE Conference on Decision and Control 2021

Kickstarting deep reinforcement learning algorithms facilitate a teacher-student relationship among the agents and allow for a well-performing teacher to share demonstrations with a student to expedite the student's training. However, despite the known benefits, the demonstrations may contain sensitive information about the teacher's training data and existing kickstarting methods do not take any measures to protect it. Therefore, we use the framework of differential privacy to develop a mechanism that securely shares the teacher's demonstrations with the student. The mechanism allows for the teacher to decide upon the accuracy of its demonstrations with respect to the privacy budget that it consumes, thereby granting the teacher full control over its data privacy. We then develop a kickstarted deep reinforcement learning algorithm for the student that is privacy-aware because we calibrate its objective with the parameters of the teacher's privacy mechanism. The privacy-aware design of the algorithm makes it possible to kickstart the student's learning despite the perturbations induced by the privacy mechanism. From numerical experiments, we highlight three empirical results: (i) the algorithm succeeds in expediting the student's learning, (ii) the student converges to a performance level that was not possible without the demonstrations, and (iii) the student maintains its enhanced performance even after the teacher stops sharing useful demonstrations due to its privacy budget constraints., Comment: Under double-blind review

Communication delays and synchronization are major bottlenecks for parallel computing, and tolerating asynchrony is therefore crucial for accelerating parallel computation. Motivated by optimization problems that do not satisfy convexity assumptions, we present an asynchronous block coordinate descent algorithm for nonconvex optimization problems whose objective functions satisfy the Polyak-Lojasiewicz condition. This condition is a generalization of strong convexity to nonconvex problems and requires neither convexity nor uniqueness of minimizers. Under only assumptions of mild smoothness of objective functions and bounded delays, we prove that a linear convergence rate is obtained. Numerical experiments for logistic regression problems are presented to illustrate the impact of asynchrony upon convergence., Comment: 6 pages, 1 figure