PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentially Private Distributed Constrained Optimization

Shuo Han, Ufuk Topcu, George J. Pappas

arXiv:1411.4105v1math.OCcs.DSeess.SY

TL;DR

The paper addresses privacy risks in distributed optimization when public coordination signals depend on sensitive user constraints. It introduces an ǫ-differentially private distributed algorithm that adds noise according to projection sensitivity, analyzes suboptimality through stochastic-gradient methods, and demonstrates the approach for EV charging. The algorithm preserves differential privacy, while the analysis and simulations characterize trade-offs among privacy, performance, user count, and iteration choice.

  • Problem

    The paper addresses privacy risks in distributed optimization when public coordination signals depend on sensitive user constraints.

  • Method

    It introduces an ǫ-differentially private distributed algorithm that adds noise to public coordination signals according to projection sensitivity.

  • Results

    The algorithm preserves ǫ-differential privacy, and EV-charging simulations show strong privacy with little performance loss when many vehicles participate.

  • Takeaways & Limitations

    The analysis and simulations characterize trade-offs among privacy, performance, user count, and iteration choice.

Abstract

from arXiv · show

Many resource allocation problems can be formulated as an optimization problem whose constraints contain sensitive information about participating users. This paper concerns solving this kind of optimization problem in a distributed manner while protecting the privacy of user information. Without privacy considerations, existing distributed algorithms normally consist in a central entity computing and broadcasting certain public coordination signals to participating users. However, the coordination signals often depend on user information, so that an adversary who has access to the coordination signals can potentially decode information on individual users and put user privacy at risk. We present a distributed optimization algorithm that preserves differential privacy, which is a strong notion that guarantees user privacy regardless of any auxiliary information an adversary may have. The algorithm achieves privacy by perturbing the public signals with additive noise, whose magnitude is determined by the sensitivity of the projection operation onto user-specified constraints. By viewing the differentially private algorithm as an implementation of stochastic gradient descent, we are able to derive a bound for the suboptimality of the algorithm. We illustrate the implementation of our algorithm via a case study of electric vehicle charging. Specifically, we derive the sensitivity and present numerical simulations for the algorithm. Through numerical simulations, we are able to investigate various aspects of the algorithm when being used in practice, including the choice of step size, number of iterations, and the trade-off between privacy level and suboptimality.

I. INTRODUCTION

The paper studies differentially private distributed constrained optimization motivated by privacy risks in EV charging, where public coordination signals depend on user information. It develops a general algorithm, analyzes its privacy-performance trade-off, and illustrates the framework for EV charging.

  • Motivation: Distributed EV charging can reduce grid impacts, but centralized computation is costly and uncoordinated charging can cause voltage deviations.The paper frames charging schedules as constrained optimization problems involving peak load, power loss, or load variance.
  • Privacy concern: Public coordination signals computed from users’ tentative demands can reveal sensitive information, such as whether a homeowner is away.Potential adversaries receive the signals and may use them to infer individual user information.
  • Contributions: The proposed algorithm adds privacy noise to public signals and proves differential privacy using adaptive composition.The paper views the private method as stochastic gradient descent to derive a suboptimality bound and expose the privacy-performance trade-off.
  • Evaluation: For EV charging, the paper computes projection sensitivity explicitly and evaluates step size, iteration count, privacy, and performance numerically.The simulations investigate how the general framework behaves in a concrete charging application.
  • Scope and novelty: The paper targets divisible-resource allocation with private information in user constraints, extending related private linear-programming work.Its objective may be any convex function of aggregate allocation with Lipschitz continuous gradients, while constraints may be convex and separable.

B. Differential privacy

This section formalizes privacy for distributed constrained optimization by treating user constraint sets as private database entries and public gradients as the query. It then specializes the formulation to EV charging, where exact gradients can expose individual charging schedules and constraints.

  • Differential privacy: Differential privacy is formulated by hiding changes between adjacent databases through a randomized mechanism whose outputs are nearly indistinguishable.The privacy parameter ǫ controls the guarantee: smaller ǫ provides higher privacy.
  • Problem formulation: The database consists of user constraint sets, while the query is the tuple of public gradients released across iterations.Each constraint set is parameterized, and adjacency permits a bounded change in one user’s constraint while others remain unchanged.
  • Problem formulation: The formal objective is to design a randomized mechanism that approximates the gradients while preserving ǫ-differential privacy under the constrained-optimization adjacency relation.The adjacency threshold reflects which user activities should remain private.
  • EV charging model: In EV charging, each vehicle’s schedule must deliver energy Ei while respecting per-time-step maximum charging rates.The charging specification is the pair (r̄i, Ei), which parameterizes the user’s feasible constraint set.
  • EV charging privacy: Publishing exact gradients can let an adversary reconstruct one user’s tentative demand and infer private constraint information when collaborating with other users.For example, inferred demand can reveal Ei, while charging specifications may encode personal activities.

IV. OVERVIEW OF MAIN RESULTS

The paper introduces a differentially private distributed projected gradient method for constrained optimization. It adds noise calibrated to projection sensitivity, preserves privacy, and supports finite-iteration suboptimality analysis.

  • General algorithm: Algorithm 2 is a differentially private distributed projected gradient descent method for constrained optimization.It modifies distributed projected gradient descent by perturbing publicly broadcast gradients.
  • General algorithm: The sensitivity bound Δ controls the noise added to the projected-gradient mechanism.Δ bounds the global ℓ2-sensitivity of each user’s projection operator.
  • Privacy guarantee: Noisy gradients form a randomized mechanism that preserves ε-differential privacy under the stated adjacency relation.The privacy guarantee is established for the sequence of noisy gradients broadcast across iterations.
  • Stochastic-gradient interpretation: Algorithm 2 can be viewed as stochastic gradient descent because its noisy gradients are unbiased estimates of the original gradients.Polynomial-decay averaging is introduced to improve convergence without affecting privacy.
  • Finite-iteration analysis: The analysis bounds expected suboptimality after a finite number K of iterations.This addresses the practical setting where iterative optimization terminates before asymptotic convergence.

B. Results for the case of EV charging

The EV-charging case study supplies the sensitivity needed to instantiate the private algorithm and connects its privacy guarantee to the Laplace mechanism and adaptive composition.

  • Sensitivity computation: For EV charging, the paper derives a bound on the global ℓ2-sensitivity of the projection operator with respect to charging specifications.The relevant changes are parameterized by δr and δE in the adjacency relation.
  • Privacy mechanism: The private gradients are produced by adding Laplace-style noise calibrated to query sensitivity.The mechanism adds noise to a numerical query according to its ℓ2-sensitivity.
  • Privacy mechanism: Adaptive sequential composition combines per-iteration privacy guarantees into the ε-differential privacy guarantee for the full gradient sequence.Each noisy gradient is treated as a mechanism whose output may depend on previous outputs.
  • Optimization procedure: The algorithm uses polynomial-decay averaging while iteratively updating projected decisions from noisy gradients.The averaging weights are θk = (η + 1)/(η + k).

C. Suboptimality analysis: Privacy-performance trade-off

The suboptimality analysis interprets privacy noise as stochastic-gradient noise and derives finite-iteration bounds that expose trade-offs among privacy, users, and runtime.

  • Analysis framework: Algorithm 2 is analyzed as stochastic gradient descent using noisy gradients rather than exact gradients.The additive noise has zero mean, making each noisy gradient an unbiased estimate of the original.
  • Finite-iteration bound: The expected suboptimality after finite K is bounded under bounded-domain and expected-gradient-norm assumptions.The stochastic-gradient result assumes a convex feasible set, convex objective, diameter bound ρ, and gradient bound bG.
  • Iteration trade-off: As K increases, one bound term decreases while another increases, implying an iteration count that minimizes the expected suboptimality bound.The paper derives a corresponding optimized-K bound by minimizing the upper bound over K.
  • Practical selection: Theoretical optimization of K is often unreliable because tight bounds for ρ and bG are generally unavailable.The paper recommends numerical simulation to select K for a given problem.

VI. SENSITIVITY COMPUTATION: THE CASE OF EV

The EV sensitivity analysis reduces projection sensitivity to parameter changes in charging limits and energy requirements. It uses local solution sensitivities, integration, and regularity conditions to obtain global bounds.

  • Projection formulation: The EV projection maps a tentative charging vector to the solution of a constrained least-squares problem.The constraints impose componentwise charging limits and a fixed total energy requirement.
  • Global sensitivity: The global sensitivity Δ is obtained by bounding how the optimal projection changes when user parameters vary.The analysis treats changes in the upper-bound vector a and energy scalar b separately before combining them.
  • Sensitivity derivation: Local solution sensitivities are derived under differentiability, regularity, and strict complementary-slackness conditions.The optimization-theory result requires a locally unique solution and linearly independent active-constraint gradients.
  • Scope and caveats: Strict complementary slackness may fail at some parameter values, although the analysis states that only finitely many such values occur along the integration path.This allows the integration-based global sensitivity calculation to proceed despite those exceptions.
  • Sensitivity derivation: Integration of local sensitivities yields global sensitivity bounds in b and a along a coordinate-wise integration path.The path varies one component of a at a time, and the relevant exceptional parameter values are finite.
  • Scope and caveats: A loose sensitivity bound causes excess gradient noise and can increase the performance loss from privacy.The paper notes that less noise is desirable for minimizing this loss.

D. Revisited: Suboptimality analysis

For the specific objective U, the paper refines the general suboptimality bound to expose how privacy-related performance depends on participating users and privacy level.

  • The refined bound substitutes objective-specific values of ρ, G, and L into the general suboptimality result.The derivation uses L = 1/m^2 = γ^2/n^2 and omits d, rmax, and γ to emphasize n and ǫ.
  • As ǫ decreases, privacy increases while suboptimality worsens because the algorithm introduces more noise.The bound characterizes this privacy–performance trade-off.
  • Increasing the number of participating users n can mitigate the suboptimality increase caused by stronger privacy.The paper relates this effect to aggregate information becoming easier to privatize as n grows.

VII. NUMERICAL SIMULATIONS

The EV-charging simulations examine implementation choices and privacy–performance behavior, finding practical sensitivity to iteration count and privacy level but limited sensitivity to the step-size constant over a tested range.

  • The simulation uses n = 100,000 EVs, m = 500,000, a 52-slot horizon, and N = 100 user groups for computational efficiency.Users in each group share initial conditions, allowing the projection to be computed once per group.
  • The privacy adjacency parameters are δr = 13.2 kW and δE = 12 kW, while L = 1/m^2 and η = 1.The δr choice targets events shorter than one hour, and δE spans the specified energy interval.
  • With ǫ = 0.1, Algorithm 2 follows the optimal charging profile but exhibits additional fluctuations from noisy gradients.Both profiles show a dip at t = 34 caused by the constraint on r̄i(t).
  • The step-size constant is insensitive over c ∈ [10, 20], so subsequent simulations use c = 10.Relative suboptimality is normalized against U* in the corresponding analysis.
  • The relative suboptimality has an optimal iteration count K; too few iterations impair convergence, whereas too many add gradient noise.This empirical pattern coincides with Theorem 7.
  • As ǫ grows and privacy becomes less stringent, relative suboptimality improves; its fitted slope is approximately −0.698 versus the theoretical −0.25.The number of iterations K is optimized for each ǫ, and the empirical rate suggests the theoretical bound is loose.

VIII. CONCLUSIONS

The paper develops a differentially private distributed constrained-optimization algorithm and demonstrates its privacy mechanism, EV-charging sensitivity analysis, and privacy–performance trade-off.

  • The algorithm protects user constraint specifications by adding noise to public gradient coordination signals.Sequential adaptive composition determines the noise magnitude through the sensitivity of the projection ΠC.
  • Projection sensitivity is computed through least-squares solution-sensitivity analysis and demonstrated for EV charging.The EV case provides an explicit sensitivity expression for the user-specified constraints.
  • For EV charging, expected suboptimality is upper bounded by O((nǫ)^−1/4), with an optimal iteration count balancing convergence and accumulated gradient noise.Simulations suggest the bound is likely not tight.

APPENDIX I PROOF OF LEMMA 13

The appendix proves the sensitivity result by analyzing the projection problem through induction, sensitivity calculations, Lagrangian conditions, and finite case partitions.

  • The proof uses induction over iterations to establish how outputs depend on neighboring private datasets.Adaptive sequential composition is used when conditioning on the previously released output.
  • It computes the ℓ2-sensitivity of the public signal after establishing the inductive dependence relations.The sensitivity calculation is stated explicitly after the induction setup.
  • The projection analysis formulates a Lagrangian and applies optimality conditions involving the associated multipliers.The argument uses strict complementary slackness to classify active and inactive constraints.
  • The proof partitions indices according to constraint activity and shows that only finitely many values of the scalar parameter can arise.The finite-partition argument covers cases where the multiplier-index sets are empty or nonempty.
  • When strict complementary slackness fails, the proof tracks the violating multiplier sets and partitions the remaining indices into three cases.These cases support the subsequent characterization of the projection solution.
  • The resulting coordinate relations express constrained components through the optimal multiplier and the reference point.The proof derives these relations separately for indices in and outside the active sets.

C. Proof of Lemma 21

Under strict complementary slackness, the proof classifies each index into three cases and evaluates the sensitivity derivatives accordingly. At most one index contributes norm 2, while all other indices contribute 0, yielding a total bound of at most 2.

  • Case analysis: The proof assumes strict complementary slackness and separates each index into three possible cases.It then derives the expression for ∥∂a_i x*∥_1 separately in each case.
  • Case analysis: When λ*_i = 0, substituting the derivative relation gives C_i = 0 and ∥∂a_i x*∥_1 = 0.This corresponds to the first case in the proof.
  • Case analysis: When x*_i = a_i and λ*_i = 1, substitution gives C_i = −1, leading to ∥∂a_i x*∥_1 = 2.The proof identifies this as the second case.
  • Case analysis: For the remaining case, strict complementary slackness and the derivative conditions imply that the corresponding derivative norm is 0.The argument uses the resulting conditions on x*_j and λ*_j to exclude incompatible configurations.
  • Conclusion: At most one index satisfies ∥∂a_i x*∥_1 = 2, whereas every other index has derivative norm 0.Thus the sum of the derivative norms is bounded by 2.

D. Proof of Lemma 22

The proof analyzes changes in the constraint parameters along an integration path where only one a_i may vary. It concludes that the equality constraint b = 1^T x* can hold at only finitely many parameter values along that path.

  • Case structure: For indices outside I_μ, one of three cases must hold.The proof introduces these cases after handling indices in I_μ.
  • Path argument: Because b and x_0 are fixed and only one a_i may change along L, the proof applies an argument analogous to Lemma 19.This establishes finiteness of the parameter values satisfying b = 1^T x*.
Loading 1411.4105v1…