Differentially Private Stochastic Convex Optimization for Network Routing Applications

In this paper we present a differentially private algorithm for network routing problems. The main ingredient is a reformulation of network routing which moves all user data dependent parameters out of the constraint set and into the objective function. We then present an algorithm for solving this formulation based on differentially private variants of stochastic gradient descent. In this algorithm, differential privacy is achieved by injecting noise, and one may wonder if this noise injection compromises solution quality. We prove that our algorithm is differentially private and under several reasonable regularity conditions, is also asymptotically optimal (as the size of the training set goes to infinity). We note that in exchange for becoming compatible with differentially private algorithms, this new formulation is more computationally expensive.

Traffic assignment in transportation systems is one of the most well-known applications of network routing. Herein we focus our literature review on privacy research in transportation networks. Privacy works in transportation mainly focus on location privacy, where the objectives is to prevent untrusted and/or external entities from learning geographic locations or location sequences of an individual [BS03]. Privacy-preserving approaches have been proposed for various location-based applications, e.g., trajectory publishing, mobile crowdsensing, traffic control, etc. These techniques are based on spatial cloaking [CML11] and differential privacy [Dwo08]. While not the setting of interest for this paper, there are many works that use Secure Multi-Party Computation (MPC) [GMW87] to achieve privacy in distributed mobility systems.

Spatial cloaking approaches aggregate users’ exact locations into coarse information. These approaches are often based on $k$-anonymity [Swe02], where a mobility dataset is divided into equivalence classes based on data attributes (e.g., geological regions, time, etc.) so that each class contains at least $k$ records [GFCA14, HC20]. These $k$-anonymity-based approaches can guarantee that every record in the dataset is indistinguishable from at least $k-1$ other records. However, $k$-anonymity is generally considered to be a weak privacy guarantee, especially when $k$ is small. Furthermore, very coarse data aggregation is required to address outliers or sparse data, and in these cases spatial cloaking-based approaches provide low data accuracy.

Differential privacy provides a principled privacy guarantee by producing randomized responses to queries, whereby two datasets that differ in only one entry produce statistically indistinguishable responses [DMNS06]. In other words, differential privacy ensures that an adversary with arbitrary background information (e.g., query responses, other entries) cannot infer individual entries with high confidence. Within transportation research, [WHL⁺18, YLL⁺19] share noisy versions of location data for mobile crowd-sensing applications. [GZFS15, GLTY18, AHFI⁺18, LYH20] use differential privacy to publish noisy versions of trajectory data. [DKBS15] and [HTP17] apply differential privacy to gradient descent algorithms for federated learning in mobility systems.

Many of the works mentioned in the previous paragraph establish differential privacy of their proposed algorithms by using composition properties of differential privacy. Composition theorems for differential privacy describe how well privacy is preserved when conducting several computations one after another. In [DKBS15] and [HTP17], composition theorems are applied as black boxes without considering the mathematical properties of the gradient descent algorithm. As a result, the privacy guarantees are overly conservative, meaning that large amounts of noise are added to the algorithm, leading to suboptimal behavior both in theory and in practice. Similarly, [GZFS15, GLTY18, AHFI⁺18, LYH20] use composition rules as a black box, and while privacy is achieved in this way, there are no accuracy guarantees for the algorithms presented in those works.

While blackbox applications of differential privacy can lead to impractical levels of noise injection, specialized applications of differential privacy were discovered that could provide privacy with much less noise. [WLK⁺17] show how a simple adjustment to stochastic gradient descent can give rise to an algorithm which is both differentially private, and under reasonable regularity assumptions, is also asymptotically optimal. [FMTT18] and [FKT20] refined this idea to develop stochastic gradient descent algorithms that are differentially private, computationally efficient, and have optimal convergence rates. These techniques cannot directly be used to solve the standard formulation of network routing because they study unconstrained optimization problems or optimization problems with public constraint sets (i.e., constraints that do not include any private data).

In this section we will introduce a) a graph model of a network, b) a representation of network demand, c) the standard formulation for network routing and d) privacy requirements. The notation defined in this section is aggregated in table form in Section A for the reader’s convenience.

In this paper we study a setting where a network operator wants to route demand while minimizing the total travel time for the requests. With these definitions, the standard formulation of minimum travle time network routing is described in Definition 5.

In (1), the decision variable $x$ is a collection of flows $\left\{x^{(o,d)}\right\}_{(o,d)\in V\times V}$, one for each non-zero entry of $\Lambda$, as represented by constraint (1b). (1d) are flow conservation constraints to ensure that $x^{(o,d)}$ sends $\Lambda(o,d)$ units of flow from $o$ to $d$. Constraints (1c) ensure that $\left\{y_{e}\right\}_{e\in E}$ represents the total amount of flow on each edge. Finally, the objective function (1a) is to minimize the total travel time as a function of total network flow.

In the next subsection we will describe the rigorous privacy requirements that we will mandate while designing algorithms for network flow. We then describe in Section 2.4 why privacy and feasibility are mutually exclusive in the standard network flow formulation.

We will use differential privacy to reason about the privacy-preserving properties of our algorithms. At a high level, changing one data point of the input to a differentially private algorithm should lead to a statistically indistinguishable change in the output. To make this concept concrete we will need to define data sets and adjacency.

While the exact definition can vary across applications, adjacent data sets are sets that are very similar to one another. The most common definition of adjacency is the following: $L,L^{\prime}$ are adjacent if and only if $L^{\prime}$ can be obtained by adding, deleting, or modifying at most one data point from $L$, and vice versa. Thus comparing a function’s output on adjacent data sets measures how sensitive the function is to changes in a single data point.

With these definitions in place, we are now ready to define differential privacy.

The definition of differential privacy requires that changing one data point in the input to a differentially private algorithm cannot change the distribution of the algorithm’s output by too much. Such a requirement ensures the following strong privacy guarantee: It is statistically impossible to reliably infer the properties of a single data point just by examining the algorithm’s output, even if the observer knows all of the other data points in the input [DMNS06].

To proceed, we must specify what data set adjacency means in the context of network routing. For network routing problems, historical data is often a collection of routing requests through the network. To protect the privacy of those who submit requests, we want the routing policy we compute to not depend too much on any single request that appears in the historical data. This motivates the the following notion of data set adjacency that we will be using throughout this paper.

In the introduction we mentioned that privacy and feasibility can be mutually exclusive in the standard formulation of network flow described in (1). In this section we formally show that if $\Lambda$ is constructed from a data set of trips as described in Remark 1, then trips to or from uncommon locations can be easily detected from any feasible solution to (1). As a result, announcing or releasing a feasible solution to (1) is not, in general, differentially private. Formally, we will prove the following theorem in this section.

We further note that $(\epsilon,\delta)$-differential privacy only provides a meaningful privacy guarantee when $\epsilon<1$ and $\delta<1$ [Dwo08].

We have two remarks regarding Theorem 1.

In the minimum travel time network flow problem, the network operator wants to find a stationary routing policy for each $(o,d)$ pair that will lead to small total travel times for the requests. Due to the equivalence between stationary $(o,d)$ routing policies and unit $(o,d)$ flows, the network operator can instead search over the space of unit $(o,d)$ flows.

The total travel time of a flow $y$ through $G$ is given by $\sum_{e\in E}y_{e}f_{e}(y_{e})$. The total flow resulting from a unit network flow $x$ serving demand $\Lambda$ is the sum of the flow contributions from each of the $(o,d)$ pairs. With Remark 5 in mind, the total amount of flow on an edge $e\in E$ when serving $\Lambda$ according to $x$ is given by $\sum_{(o,d)\in V\times V}\Lambda(o,d)x_{e}^{(o,d)}$. We can thus define $F(x,\Lambda)$, the total travel time experienced by requests $\Lambda$ when being routed by $x$, as follows:

With these definitions in place, the unit network flow that minimizes the total travel time when serving the demand $\Lambda$ can be found by solving the following optimization problem

In practice, demand may vary from day to day, and such variations can be modeled by $\Lambda$ being a random variable with distribution $\mathcal{Q}$. If $\mathcal{Q}$ is known by the network operator, then rather than solving (8), the operator is interested in minimizing expected total travel time through the following stochastic optimization problem:

We note that (9) is a generalization of (1) to the case when $\Lambda$ is random.

In the more realistic case that $\mathcal{Q}$ is not known, the optimization problem (9) can be approximated from historical data. We study a situation where the network operator has demand data $\Lambda_{1},\Lambda_{2},...,\Lambda_{N}\overset{\text{i.i.d}}{\sim}\mathcal{Q}$ collected from operations of previous days. Using this data it can solve the following empirical approximation to (9):

The optimization problem in (10) uses historical data to estimate (9). In line with Assumption 1 we will assume that $\Lambda_{t}(o,d)\leq\lambda_{\max}$ for all values of $t,o$ and $d$.

In Section 4 we show how (10) can be solved in a request-level differentially private way.

In this section we will introduce some assumptions that will help us establish our technical results. We will make the following assumptions on the network demand:

In this section, we present a transportation network model that satisfies Assumptions 3,4,5 and 6. We study a network where the link latency functions are all affine where for each $e\in E$, there are non-negative constants $q_{e},c_{e}$ so that $f_{e}(y)=q_{e}y+c_{e}$. Let $Q\in\mathbb{R}^{m\times m}$ be defined so that $Q_{ee}=q_{e}$, and let $c\in\mathbb{R}^{m}$ be the concatenation of all of the zero order coefficients in the link latency functions.

As mentioned in Remark 4, we will represent $x$ as a concatenation of $\left\{x^{(o,d)}\right\}_{(o,d)\in V\times V}$. As such, $x\in\mathbb{R}^{n^{2}m}$. Let $\left\{(o_{i},d_{i})\right\}_{i=1}^{n^{2}}$ be the order in which the unit $(o,d)$ flows are concatenated to produce $x$ so that

The total flow on the links in the network when serving demand $\Lambda$ according to $x$ can then be written as:

where $B_{\Lambda}=\text{vec}(\Lambda)\otimes I_{m}$. Here $\text{vec}(\Lambda)$ is a $n^{2}$ dimensional row vector whose $i$th entry is $\Lambda(o_{i},d_{i})$, and $\otimes$ represents the Kronecker product. Then when $\Lambda$ is being routed according to $x$, the travel times on the links can be computed as

which means that the total travel time can be written as

If we add a bit of $\ell_{2}$ regularization, we obtain

Recall that we use $H(\cdot,\Lambda)$ to denote the hessian of $F(\cdot,\Lambda)$ with respect to its first argument. We now make the following observations:

• •

  The Hessian of $F(x,\Lambda)$ with respect to $x$ is defined for all $x$ and is equal to $2B_{\Lambda}^{\top}QB_{\Lambda}+\alpha I$. Hence Assumption 3 is satisfied.

• •

  Since $Q$ is a diagonal matrix with non-negative entries, $Q\succeq 0$. This implies that $B_{\Lambda}^{\top}QB_{\lambda}\succeq 0$. Hence $H(x,\Lambda)\succeq\alpha I$. This implies that $F$ is $\alpha$-strongly convex, and hence Assumption 4 is satisfied.

• •

  Note that $\left|\left|B_{\Lambda}^{\top}QB_{\Lambda}+(\alpha/2)I\right|\right|_{op}\leq\left|\left|Q\right|\right|_{op}\left|\left|B_{\Lambda}\right|\right|_{op}^{2}+\alpha/2\leq\left|\left|Q\right|\right|_{op}\left|\left|\text{vec}(\Lambda)\right|\right|_{2}^{2}\left|\left|I_{m}\right|\right|_{op}^{2}+\alpha/2$. Defining $\beta:=n^{2}\left(\max_{e}q_{e}\right)\lambda_{\max}^{2}+\alpha/2$, we see that $\left|\left|H(x,\Lambda)\right|\right|_{op}\leq\beta$ for all $x\in\mathcal{X}$, meaning that $F$ is $\beta$-smooth, and thus Assumption 5 is satisfied.

• •

  By product rule,

  	$\displaystyle\mathcal{D}_{\Lambda(o_{i},d_{i})}\left[\nabla F\right](x,\Lambda)$	$\displaystyle=\frac{\partial}{\partial\Lambda(o_{i},d_{i})}\left\{2\left(B_{\Lambda}^{\top}QB_{\Lambda}+\alpha I\right)x+B_{\Lambda}^{\top}c\right\}$
  		$\displaystyle=\frac{\partial}{\partial\Lambda(o_{i},d_{i})}\left\{2B_{\Lambda}^{\top}Qy+2\alpha x+B_{\Lambda}^{\top}c\right\}$
  		$\displaystyle=2\left((e_{i}\otimes I)Qy+B_{\Lambda}^{\top}Qx^{(o,d)}\right)+e_{i}\otimes c$

  where $e_{i}$ is the $i$th standard basis vector for $\mathbb{R}^{n^{2}}$. By triangle inequality we can then conclude that

  	$\displaystyle\left|\left|\mathcal{D}_{\Lambda(o_{i},d_{i})}\left[\nabla F\right](x,\Lambda)\right|\right|_{2}$	$\displaystyle\leq 2\left|\left|Qy\right|\right|_{2}+2\left|\left|B_{\Lambda}^{\top}Qx^{(o,d)}\right|\right|_{2}+\left|\left|c\right|\right|_{2}$
  		$\displaystyle\leq 2\left|\left|Q\right|\right|_{op}\left|\left|y\right|\right|_{2}+2\left|\left|B_{\Lambda}\right|\right|_{op}\left|\left|Q\right|\right|_{op}\left|\left|x^{(o,d)}\right|\right|_{2}+\left|\left|c\right|\right|_{2}$
  		$\displaystyle\overset{(a)}{\leq}2\left|\left|Q\right|\right|_{op}\left|\left|y\right|\right|_{2}+2n\lambda_{\max}\left|\left|Q\right|\right|_{op}\sqrt{m}+\left|\left|c\right|\right|_{2}$
  		$\displaystyle\overset{(b)}{\leq}2\lambda_{\max}\left|\left|Q\right|\right|_{op}n^{2}\sqrt{m}+2\lambda_{\max}\left|\left|Q\right|\right|_{op}n\sqrt{m}+\left|\left|c\right|\right|_{2}.$

  Here $(a)$ is due to the fact that $x^{(o,d)}$ is a unit $(o,d)$ flow, meaning $\left|\left|x^{(o,d)}\right|\right|_{\infty}\leq 1$ and thus $\left|\left|x^{(o,d)}\right|\right|_{2}\leq\sqrt{m}$. Also, $B_{\Lambda}=\text{vec}(\Lambda)\otimes I_{m}$ implies that $\left|\left|B_{\Lambda}\right|\right|_{op}\leq\left|\left|\mathds{1}_{m}^{\top}\right|\right|_{2}\left|\left|I_{m}\right|\right|_{op}=n\lambda_{\max}$. $(b)$ is due to $\left|\left|y\right|\right|_{2}=\left|\left|B_{\Lambda}x^{(o,d)}\right|\right|_{2}\leq\left|\left|B_{\Lambda}\right|\right|_{op}\left|\left|x^{(o,d)}\right|\right|_{2}\leq n^{2}\sqrt{m}\lambda_{\max}$.

  Hence Assumption 6 is satisfied with $C=2\lambda_{\max}\left|\left|Q\right|\right|_{op}\sqrt{m}n(n+1)+\left|\left|c\right|\right|_{2}$.

Carefully adding noise to specific parts of existing algorithms is a principled approach for developing differentially private algorithms [DMNS06, FMTT18, FKT20]. The main challenge in such an approach is determining a) where and b) how much noise to add. Suppose the goal is to (approximately) compute a query function $f(L)$ on a data set $L$ in a differentially private way. The latter question can be addressed by measuring the sensitivity of the desired query function.

Once the sensitivity of the query function is known, the required noise distribution can be determined using the Gaussian mechanism as described in Theorem 4.

Calculating the sensitivity of the simple query functions (e.g., counting, voting, selecting the maximum value) is relatively easy, making the Gaussian mechanism straightforward to apply. However, for more complicated functions, noise calibration becomes more involved.

Algorithm 1 is an application of the Gaussian mechanism. Moreover, Theorem 3 shows that the suboptimality of Algorithm 1 is $O\left(\frac{1}{\sqrt{N}}\right)$. The asymptotic optimality of Algorithm 1 comes from the fact that the $\ell_{2}$ sensitivity of the final gradient descent iterate is actually converging to zero as $N$ approaches infinity. This fact enables us to add less noise as $N\rightarrow\infty$. Indeed, the Gaussian noise added to the final gradient descent iterate in Algorithm 1 has standard deviation which is $O\left(\frac{1}{N}\right)$.

In the remainder of this section, we sketch some of the mathematical ideas behind the perhaps non-intuitive result that the sensitivity of gradient descent converges to zero as the number of data points increases. For simplicity of exposition we will a) use scalar notation in place of vector notation for the sake of readability, and b) consider the simpler case of unconstrained gradient descent, which removes the need to perform projections. As a reminder, the full proof can be found in Appendix B.

Given a mobility data set, we use $x_{t}(L)$ to denote the $t$-th iterate of Algorithm 1 when using data set $L$. It is sufficient to show that the $\max_{t}\left|\frac{dx_{N}}{d\Lambda_{t}}\right|$ converges to zero for every $t$. This is because the sensitivity is obtained by integrating the derivative:

Because $L_{1},L_{2}$ are adjacent, the distance between them is finite, and thus the above integral will converge to zero if its integrand converges to zero.

With this in mind, by chain rule, we can write