PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentially Private Distributed Convex Optimization via Functional Perturbation

Erfan Nozari, Pavankumar Tallapragada, Jorge Cortés

arXiv:1512.00369v3math.OCmath.DS

TL;DR

The paper asks how distributed convex optimization can protect agents’ objective functions without sacrificing noise-free accuracy. It proves that message perturbation fails under asymptotically stable noiseless dynamics, then develops functional perturbation with privacy-preserving post-processing and optimizer-error bounds. The resulting framework supports distributed optimization on noisy functions and characterizes the privacy–accuracy trade-off.

  • Problem

    Distributed agents need to minimize a sum of local objectives while keeping each objective function private.

  • Method

    The paper perturbs individual functions with Laplace noise, defines functional differential privacy, and applies smoothening and projection post-processing before distributed optimization.

  • Results

    Message-perturbing strategies cannot guarantee differential privacy when the underlying noiseless dynamics are locally asymptotically stable.

  • Takeaways & Limitations

    Functional perturbation preserves privacy while allowing coordination algorithms to operate on regularized noisy objectives and recover perfect accuracy without noise.

  • Takeaways & Limitations

    The impossibility result concerns message-perturbing algorithms whose underlying noiseless dynamics are locally asymptotically stable.

Abstract

from arXiv · show

We study a class of distributed convex constrained optimization problems where a group of agents aim to minimize the sum of individual objective functions while each desires that any information about its objective function is kept private. We prove the impossibility of achieving differential privacy using strategies based on perturbing the inter-agent messages with noise when the underlying noise-free dynamics are asymptotically stable. This justifies our algorithmic solution based on the perturbation of individual functions with Laplace noise. To this end, we establish a general framework for differentially private handling of functional data. We further design post-processing steps that ensure the perturbed functions regain the smoothness and convexity properties of the original functions while preserving the differentially private guarantees of the functional perturbation step. This methodology allows us to use any distributed coordination algorithm to solve the optimization problem on the noisy functions. Finally, we explicitly bound the magnitude of the expected distance between the perturbed and true optimizers which leads to an upper bound on the privacy-accuracy trade-off curve. Simulations illustrate our results.

I. INTRODUCTION

The paper targets privacy-preserving distributed optimization for networked agents while maintaining high accuracy. It identifies limitations of message perturbation and proposes functional perturbation with privacy-preserving regularization and accuracy analysis.

  • Distributed optimization in cyberphysical systems can expose sensitive objective functions, optimizer estimates, or constraints.
  • Prior distributed convex optimization research generally does not address privacy, while private distributed methods commonly perturb inter-agent messages.
  • Message perturbation can create steady-state accuracy error and bias unrelated to the added noise when the underlying noiseless dynamics lack asymptotic stability.
  • The paper proves that noise-perturbing coordination algorithms cannot satisfy differential privacy when their underlying noiseless dynamics are locally asymptotically stable.
  • The proposed functional-perturbation framework uses smoothening and projection steps to recover regularity while preserving privacy, and bounds expected optimizer deviation.

III. PROBLEM STATEMENT

The problem is to design distributed optimization algorithms that protect agents’ local objective functions while retaining accuracy. The formulation assumes convex local objectives over a shared compact feasible set and requires exact recovery of the aggregate optimizer without privacy noise.

  • Each agent owns a convex, twice continuously differentiable local objective over a convex compact domain with nonempty interior.
  • The feasible set is treated as global information known to all agents.
  • The group seeks to minimize the aggregate objective through neighbor-only communication while keeping each local objective function confidential.
  • Differential privacy requires output statistics to change only slightly when one agent’s objective changes within the chosen adjacency space.
  • The design goal is accuracy that improves as privacy is relaxed and reaches the exact optimizer without privacy.
  • Distributed algorithms can converge asymptotically to the optimizer under connectivity assumptions and square-summable stepsizes, motivating privacy guarantees for their execution.

IV. RATIONALE FOR DESIGN STRATEGY

The paper contrasts message perturbation with objective-function perturbation and shows why asymptotically stable message-based dynamics cannot preserve differential privacy. This impossibility motivates functional perturbation, while decaying-noise conditions and a stability argument characterize the limitation.

  • Message-perturbing strategy: Message-perturbing strategies add Gaussian or Laplace noise to agents’ transmitted messages while retaining the original distributed algorithm.The generic strategy modifies messages sent to neighbors or a central aggregator.
  • Noise behavior: For independent Laplace or Gaussian noise with b(k)=O(1/k^p), p>0, the noise converges to zero almost surely and remains bounded with positive probability.The result follows from the stated decaying-variance condition and associated event probabilities.
  • Impossibility result: Under 0-LAS dynamics, distinct information sets with different optimizers produce trajectories whose privacy-relevant noise events have incompatible probabilities.The proof uses a bijection between message and perturbation sequences and compares convergence to the equilibria associated with the two information sets.
  • Impossibility result: Consequently, a message-perturbing algorithm with asymptotically stable noise-free dynamics cannot satisfy ϵ-differential privacy for any ϵ>0.The proposition applies when the stated stability and neighborhood conditions hold.
  • Design rationale: The result includes continuous globally asymptotically stable dynamics and motivates perturbing objective functions rather than inter-agent messages.The paper identifies message perturbation as limited when privacy requires asymptotically vanishing noise, while the broader design discussion turns to objective perturbation.

B. Algorithm Design via Objective Perturbation

The paper proposes perturbing agents’ objective functions rather than inter-agent messages, then applying distributed optimization to the perturbed functions while preserving differential privacy through post-processing.

  • Objective perturbation lets agents independently privatize their functions before participating in distributed optimization.
  • The proposed strategy leaves the coordination stepsizes unchanged while replacing original objectives with perturbed functions.
  • Post-processing preserves differential privacy when measurable maps are applied to the functional perturbation output.
  • The design must establish private function perturbation and ensure that perturbed functions retain the smoothness and regularity required for convergence.

V. FUNCTIONAL DIFFERENTIAL PRIVACY

Functional differential privacy protects sensitive functional data by perturbing function coefficients with noise, subject to conditions ensuring the perturbed representation remains well defined.

  • Functional differential privacy applies when sensitive information is a function or function attributes such as sample points, optimizers, derivatives, and integrals.
  • The mechanism decomposes an L2(D) function into coefficients and adds noise to every coefficient.
  • The noise-scale sequence cannot be arbitrary because the perturbation must belong to ℓ2 and its reconstructed series must converge.
  • Under the stated conditions, the perturbed coefficient sequence belongs to ℓ2 with probability one.
  • The proof uses exponential-tail behavior and asymptotic bounds to establish the required convergence conditions.

B. Differential Privacy of Functional Perturbation

The paper defines a weighted coefficient-space adjacency relation and chooses noise scales that make functional perturbation differentially private while keeping the mechanism well defined.

  • The adjacency space Vq is constructed as the image of a weighted ℓ2 space under the coefficient reconstruction map.
  • The resulting functional perturbation mechanism is differentially private for an appropriately chosen noise-scale sequence.
  • The proof compares functions whose difference lies in Vq and analyzes measurable output sets using the first K coefficients.
  • The noise construction is well defined because the sufficient boundedness condition ensures η belongs to ℓ2 almost surely.
  • Decreasing q enlarges the adjacency space but requires larger noise and increases the guaranteed upper bound on expected minimizer deviation.

VI. DIFFERENTIALLY PRIVATE DISTRIBUTED OPTIMIZATION

The optimization framework assumes smooth local objectives and post-processes perturbed functions so distributed coordination algorithms can use functions with the required smoothness and regularity.

  • The agents’ local objective functions belong to a class of twice continuously differentiable functions with bounded gradients and Hessians.
  • Post-processing is needed because functional perturbation may produce functions that are neither smooth nor convex.
  • Smoothening uses the density of S0 in L2(D) to approximate any perturbed function arbitrarily closely by a smooth function.
  • The approximation tolerance ε is a design parameter that can be chosen sufficiently small so coordination accuracy is not affected.
  • When basis functions are smooth, truncating the infinite expansion provides a natural smoothening step and is necessary for practical implementations.

2) Ensuring Strong Convexity and Bounded Hessian:

The paper constructs a function class that is convex and closed under the 2-norm, enabling projection of perturbed functions back into functions with strong convexity and bounded Hessian and gradient.

  • Projection: Projection from S0 onto S is well defined and provides the best approximation of a function h ∈ S0.Because S is convex and closed, its projection is unique; the projected function has bounded gradient and Hessian.
  • Convexity and closedness: S is convex because convex combinations preserve the Hessian bounds defining S1.The Hessian of a convex combination remains between αI_d and βI_d.
  • Convexity and closedness: S is closed in S0 under the 2-norm, including the gradient-bounded component S2.The proof uses subsequence convergence, almost-uniform convergence, and local gradient bounds to retain membership in S2.
  • Function-class construction: S is defined by uniformly bounded Hessians and gradients, with S = S1 ∩ S2.S1 imposes αI_d ≤ ∇²h(x) ≤ βI_d, while S2 imposes |∇h(x)| ≤ u.

B. Algorithm Design and Analysis

Agents perturb their objective functions locally with Laplace noise, post-process the results, and then apply distributed coordination without adding noise to inter-agent messages. The resulting framework preserves privacy and bounds optimizer error through a privacy-accuracy trade-off.

  • Algorithm design: Agents locally perturb their objective functions and use the modified functions without adding noise to inter-agent messages.After post-processing, agents can participate in any distributed optimization algorithm using the modified objectives.
  • Accuracy analysis: The accuracy analysis connects the distributed algorithm’s output to the optimizer of the original problem through the perturbed optimizer.The result establishes the connection between algorithm accuracy and the design parameters.
  • Privacy and convergence: Theorem VI.3 preserves ε_i-differential privacy while allowing any distributed coordination algorithm that converges to the perturbed aggregate optimizer.The theorem assumes Laplace perturbations with specified parameters and asymptotic convergence to ˜x*.
  • Privacy-accuracy trade-off: Corollary VI.4 gives an explicit privacy-accuracy trade-off under the hypotheses of Theorem VI.3.The trade-off follows by direct substitution into the accuracy bound.
  • Privacy-accuracy trade-off: The smoothing parameter can be chosen negligible relative to the privacy-dependent term, and arbitrarily large ε_i recovers perfect accuracy without privacy requirements.The parameters q_i and ε_i are selected independently, determining γ_i through the stated relation.
  • Accuracy bound refinement: A less conservative accuracy bound is available when the objective minimizers lie sufficiently far from the boundary of X.This condition is formalized through Corollary A.3 and requires sufficiently small perturbation noise.

VII. SIMULATIONS

Simulations evaluate the proposed method across privacy levels and truncation orders. Accuracy improves as privacy is relaxed, while higher truncation orders lower the smoothing-induced saturation error at greater computational cost.

  • Simulation setup: The simulations use D = X = [−5, 5]^2, n = 10, N_d = 100, λ = 0.01, and truncation orders 2, 6, and 14.These truncations produce coefficient spaces of dimensions 15, 28, and 120, respectively.
  • Simulation setup: The experiment computes perturbed and original optimizers with an iterative interior-point algorithm rather than implementing a specific distributed coordination algorithm.These optimizers represent the asymptotic behavior of provably correct distributed algorithms using the perturbed and original functions.
  • Results: Figure 2 plots |˜x* − x*| against ε for multiple truncation orders, together with fitted curves and Corollary VI.4’s theoretical upper bound.Privacy levels are swept logarithmically over [10^-2, 10^3], with 20 repetitions for each ε and truncation order.
  • Results: Accuracy improves as ε increases until the smoothing or truncation term dominates, producing a saturation level that decreases with higher truncation order.Increasing truncation order improves accuracy but increases computational complexity.
  • Comparison: The proposed method’s accuracy keeps improving with increased ε, unlike the nearly ε-insensitive accuracy observed for the message-perturbing comparison.The paper cautions that fixed-ε error values across Figures 1 and 2 are not directly comparable because ε is defined differently.
  • Conclusion: The paper concludes that function perturbation supports privacy-aware distributed optimization with the stated privacy and accuracy behavior.The conclusion reiterates the incompatibility of differential privacy with asymptotically stable noise-free message-perturbing dynamics.

APPENDIX A K-LIPSCHITZ PROPERTY OF THE argmin MAP

The appendix establishes a K-Lipschitz property for the argmin map over a class of strongly convex, smooth functions on convex compact domains. It also provides a less conservative result when minimizers lie sufficiently far from the boundary.

  • Motivation and domain geometry: The appendix studies the Lipschitz behavior of argmin because argmin is not continuous for arbitrary C2 functions.The result supports the accuracy analysis of the proposed differentially private algorithms.
  • Motivation and domain geometry: Lemma A.1 guarantees a uniformly positive portion of balls contained in any convex compact domain with nonempty interior.The domain’s inradius provides the geometric basis for the lower bounds used later.
  • Argmin Lipschitzness: Proposition A.2 establishes a K-Lipschitz bound for argmin on the function class S.The bound depends on domain geometry and the strong-convexity and smoothness parameters through κ_{α,β}.
  • Argmin Lipschitzness: The proof compares two functions’ minimizers using strong-convexity and smoothness inequalities over a geometrically selected ball.Gradient and Hessian bounds control the resulting integral lower bound in the L2 norm.
  • Large-domain refinement: When minimizers are sufficiently far from the boundary, gradients need not be uniformly bounded to obtain a less conservative argmin Lipschitz characterization.Corollary A.3 applies under Hessian bounds and an inball condition on the domain.
Loading 1512.00369v3…