Linear programming is a fundamental tool in a wide range of decision systems. However, without privacy protections, sharing the solution to a linear program may reveal information about the underlying data used to formulate it, which may be sensitive. Therefore, in this paper we introduce an approach for protecting sensitive data while formulating and solving a linear program. First, we prove that this method perturbs objectives and constraints in a way that makes them differentially private. Then, we show that (i) privatized problems always have solutions, and (ii) their solutions satisfy the constraints in their corresponding original, non-private problems. The latter result solves an open problem in the literature. Next, we analytically bound the expected sub-optimality of solutions that is induced by privacy. Numerical simulations show that, under a typical privacy setup, the solution produced by our method yields a 65% reduction in sub-optimality compared to the state of the art.

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 correlated noise levels and graph sizes.

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.

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 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 6 percent when comparing private versus non-private implementations of communication. By contrast, the team’s performance decreases by 88 percent when using baseline policies that ignore total correlation and only optimize team performance.

We present spectral differential privacy (SpDP), a novel form of differential privacy (DP) designed to protect the frequency content of time-series data that come from wide sense stationary (WSS) stochastic processes. This notion is motivated by privacy needs in applications with time-series data over unbounded time, such as smart meters. First, a notion of DP on the space of (discretized) spectral densities is introduced. A Gaussian-like mechanism for SpDP is then presented that provides DP to the spectral density. Next, a novel streaming implementation is developed to enable real-time use of the proposed mechanism. The privacy guarantee provided by SpDP is independent of the time duration over which data are collected or shared. In contrast, time-domain trajectory-level DP (TrDP) will require noise with large variance to provide privacy over an extended time duration. The technique is numerically evaluated using smart meter data from a single home to compare the utility of SpDP to that of time-domain TrDP. The noise added by SpDP is substantially smaller than that added by time-domain TrDP, particularly when privacy over long time horizons is sought by TrDP.

As members of network systems share more information among agents and with network providers, sensitive data leakage raises privacy concerns. Motivated by such concerns, we introduce a novel mechanism that privatizes vectors belonging to the unit simplex. Such vectors can be found in many applications, such as privatizing a decision-making policy in a Markov decision process. We use differential privacy as the underlying mathematical framework for this work. The introduced mechanism is a probabilistic mapping that maps a vector within the unit simplex to the same domain using a Dirichlet distribution. We find the mechanism well-suited for inputs within the unit simplex because it always returns a privatized output that is also in the unit simplex. Therefore, no further projection back onto the unit simplex is required. We verify and quantify the privacy guarantees of the mechanism for three cases: identity queries, average queries, and general linear queries. We establish a trade-off between the level of privacy and the accuracy of the mechanism output, and we introduce a parameter to balance the trade-off between them. Numerical results illustrate the proposed mechanism.

We consider a cloud-based control architecture for a linear plant with Gaussian process noise, where the state of the plant contains a client's sensitive information. We assume that the cloud tries to estimate the state while executing a designated control algorithm. The mutual information between the client's actual state and the cloud's estimate is adopted as a measure of privacy loss. We discuss the necessity of uplink and downlink privacy masks. After observing that privacy is not necessarily a monotone function of the noise levels of privacy masks, we discuss the joint design procedure for uplink and downlink privacy masks. Finally, the trade-off between privacy and control performance is explored.