PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentially Private Combinatorial Optimization

Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, Kunal Talwar

arXiv:0903.4510v2cs.DScs.CRcs.GT

TL;DR

The paper asks whether useful combinatorial optimization remains possible when client or other individual input data must remain private. It develops differential-private algorithms, alternative private representations, and matching lower bounds across several optimization problems. The results show that many such problems admit good private approximations, although amplification can introduce additional logarithmic privacy-related loss.

  • Problem

    Sensitive inputs can reveal individual information through optimization outputs, raising whether nontrivial approximate solutions can be computed privately.

  • Method

    The paper systematically designs differential-private algorithms for combinatorial optimization, using new efficient techniques, sophisticated exponential-mechanism applications, and implicit solution representations.

  • Results

    Many studied problems admit good private approximations; the paper also proves tight lower bounds and matching inefficient algorithms, including an Ω(1/ε) vertex-cover guarantee.

  • Takeaways & Limitations

    Differential privacy can support useful approximate combinatorial optimization even when explicitly revealing a solution would leak sensitive information.

  • Takeaways & Limitations

    Repeating an expected-guarantee private algorithm T times degrades privacy linearly with T and can cause an additional logarithmic loss when reducing failure probability.

Abstract

from arXiv · show

Consider the following problem: given a metric space, some of whose points are "clients", open a set of at most $k$ facilities to minimize the average distance from the clients to these facilities. This is just the well-studied $k$-median problem, for which many approximation algorithms and hardness results are known. Note that the objective function encourages opening facilities in areas where there are many clients, and given a solution, it is often possible to get a good idea of where the clients are located. However, this poses the following quandary: what if the identity of the clients is sensitive information that we would like to keep private? Is it even possible to design good algorithms for this problem that preserve the privacy of the clients? In this paper, we initiate a systematic study of algorithms for discrete optimization problems in the framework of differential privacy (which formalizes the idea of protecting the privacy of individual input elements). We show that many such problems indeed have good approximation algorithms that preserve differential privacy; this is even in cases where it is impossible to preserve cryptographic definitions of privacy while computing any non-trivial approximation to even the_value_ of an optimal solution, let alone the entire solution. Apart from the $k$-median problem, we study the problems of vertex and set cover, min-cut, facility location, Steiner tree, and the recently introduced submodular maximization problem, "Combinatorial Public Projects" (CPP).

1 Introduction

The paper initiates a systematic study of differential privacy for combinatorial optimization, asking how to balance solution utility with protection of sensitive input data. It develops private algorithms and lower bounds across several problems, including cases where explicit solutions can themselves leak information.

  • Research scope: The paper studies differential privacy for combinatorial optimization problems whose inputs may encode sensitive individual information.The scope includes k-median, vertex and set cover, min-cut, facility location, Steiner tree, and Combinatorial Public Projects.
  • Algorithmic approach: Efficient private algorithms require new ideas because the exponential mechanism cannot be applied directly when algorithms must output approximate solutions.The paper develops private algorithms for search problems that produce solutions, not merely estimates of optimal values.
  • Private representations: Explicitly outputting a vertex cover can reveal nonedges, so the paper privately outputs an orientation that implicitly represents a small cover.Each edge is covered by the endpoint it points to, and similar representational issues arise for set cover.
  • Lower bounds: Any ε-differentially private vertex-cover algorithm has approximation guarantee Ω(1/ε), and the paper gives computationally inefficient algorithms matching its lower bounds.The matching guarantees show the lower bounds are tight regardless of computational efficiency.
  • Broader implications: For Combinatorial Public Projects, differential privacy achieves the best non-truthful algorithm's approximation factor plus an additive logarithmic loss.This contrasts with the prior result that truthful and efficient approximation cannot both be achieved simultaneously.
  • Amplification: The paper introduces a private amplification lemma that converts expected utility guarantees into high-probability guarantees efficiently and privately.The lemma answers an open question posed by Feldman et al.

2 Definitions

The paper defines differential privacy as stability under one-person input changes and uses the exponential mechanism to privately select high-scoring discrete outputs.

  • Differential Privacy: Differential privacy requires outcome probabilities to remain nearly unchanged when one input element is added, removed, or altered.The paper also gives an approximate variant with a small additive δ term.
  • Differential Privacy: Differentially private computations compose: sequential mechanisms remain private with ε equal to the sum of their privacy parameters.Later computations may depend on earlier private outputs, allowing repeated private steps.
  • The Exponential Mechanism: The exponential mechanism privately selects among arbitrary candidate outputs using a score function that favors high-scoring results.Its privacy depends on the score sensitivity Δ, with guarantee 2εΔ-differential privacy.
  • The Exponential Mechanism: Highly suboptimal outputs receive exponentially small probability under the exponential mechanism.Outputs below the maximum score by a sufficiently large margin have cumulative probability at most exp(−t).

3 Private Min-Cut

The private min-cut algorithm combines graph augmentation with the exponential mechanism to obtain a near-optimal cut while preserving privacy. Its additive O(log n/ε) error is essentially unavoidable, even for computationally inefficient algorithms.

  • Algorithm and Guarantee: The algorithm outputs a cut within additive O(log n/ε) edges of the non-private optimum.Minimum cut is exactly solvable without privacy, but an exact private output can violate privacy.
  • Algorithm and Guarantee: The algorithm first privately adds edges to raise the minimum cut, then applies the exponential mechanism over candidate cuts.Karger’s bound on near-minimum cuts controls the number of competing outputs; an efficient version samples cuts generated by repeated Karger runs.
  • Algorithm and Guarantee: The expected cut cost is at most OPT + O(ln n/ε).The construction selects a suitably augmented graph and then controls the probability of choosing cuts far above its optimum.
  • Privacy: The basic algorithm preserves 2ε-differential privacy, while the efficient implementation achieves approximate differential privacy.The efficient variant restricts sampling to polynomially many near-minimum cuts and incurs a small δ term.
  • Lower Bound: Any ε-differentially private min-cut algorithm must incur expected additive Ω(ln n/ε) cost over OPT.This lower bound is information-theoretic and therefore applies regardless of computational efficiency.

4 Private k-Median

The paper develops private algorithms for metric k-median using the exponential mechanism, including an efficient local-search method. It also establishes computational and information-theoretic limits on private approximation.

  • Problem and Bounds: Private k-median selects k medians from a public metric space to minimize the total distance from private demand points.The metric diameter Δ bounds the sensitivity of the cost function.
  • Inefficient Algorithm: An inefficient exponential-mechanism algorithm achieves expected cost OPT + O(kΔ log n/ε).It directly selects a set of k facilities from all possible subsets.
  • Efficient Algorithm: With probability 1 − O(1/poly(n)), the efficient algorithm returns cost at most 6OPT + O(Δk^2 log^2 n/ε) while preserving ε-differential privacy.Privacy follows from composing the private swap selections and final selection.
  • Lower Bound: Any ε-differentially private k-median algorithm must incur additive Ω(Δ·k ln(n/k)/ε) cost on some inputs.The lower bound is independent of computational constraints and applies to private algorithms generally.
  • Facility Location: Private uniform facility location has approximation ratio Ω(√n) when a 1-differentially private algorithm outputs the chosen facilities.The construction uses a uniform metric with unit facility-opening cost.

5 Vertex Cover

The paper develops a differentially private algorithm for vertex cover that outputs an implicit cover through an edge orientation, achieving a (2 + 16/ε)-approximation. It proves privacy, extends the approach to weighted vertex cover, and establishes an Ω(1/ε) lower bound for private edge-orientation algorithms.

  • Problem: The private input is the presence or absence of each edge, while the goal is a minimum-size vertex cover.Unlike min-cut, private data defines hard feasibility constraints rather than only affecting the objective.
  • Algorithm: The algorithm privately outputs a permutation, selecting for each edge the endpoint appearing first to define an implicit vertex cover.Equivalently, it outputs an orientation whose pointed-to endpoints form a cover.
  • Algorithm: Vertices are sampled sequentially with probability proportional to uncovered degree plus a weight w_i, where w_i = (4/ε) × (n/(n − i + 1))^1/2.The added weight mixes degree-proportional selection with a uniform component, and it increases as the number of remaining vertices decreases.
  • Guarantees: The algorithm satisfies ε-differential privacy and has expected approximation factor at most 2 + 16/ε.The more general accuracy bound is (2 + 2 avg_i≤n w_i) × |OPT(G)| ≤ (2 + 16/ε)|OPT(G)|.
  • Weighted vertex cover: The weighted vertex cover extension preserves O(ε) differential privacy and achieves an O(1/ε) approximation.It adapts degree-proportional sampling by dividing uncovered degree by vertex weight.
  • Lower bound: Any ε-differentially private algorithm that prescribes edge orientations must incur an Ω(1/ε) approximation guarantee.A repeated star construction yields instances where the private method’s cost is 1/ε times the optimum.

6 Set Cover

The section develops private set-cover algorithms that output implicit permutations rather than explicit covers, analyzing inefficient and efficient variants for unweighted and weighted instances.

  • The private input is the subset R of elements to cover, while the set system (U, S) is public.
  • Unweighted Set Cover: An inefficient exponential-mechanism algorithm outputs a permutation in time O(m!poly(n)) with an O(log(em/OPT)/ǫ)-approximation.
  • Unweighted Set Cover: The efficient unweighted algorithm modifies greedy selection by using the exponential mechanism to favor sets covering many remaining elements.
  • Unweighted Set Cover: For ǫ < 1 and δ = 1/poly(n), the efficient unweighted algorithm achieves an O(ln n ln m/ǫ)-approximation while preserving (ǫ, δ)-differential privacy.
  • Weighted Set Cover: The weighted algorithm achieves cost O(T log n OPT) except with probability 1/poly(m), and preserves (ǫ, δ)-differential privacy.
  • Lower Bound: Any ǫ-differentially private algorithm mapping elements to sets must incur approximation factor Ω(log m/ǫ) on some instances, ruling out additive approximations as well.

7 Facility Location

The facility-location algorithm privatizes noisy counts on an oblivious hierarchical tree, producing an implicit facility assignment with a polylogarithmic cost guarantee.

  • Facility location minimizes connection costs plus a uniform facility cost f for private demand points D in a metric space.
  • Tree Construction: An FRT distribution supplies rooted 2-HSTs with expected stretch O(log n) and L = O(log ∆) levels.
  • Output Representation: Facilities are represented implicitly by a tree and facility set, assigning each demand to its lowest-level ancestor facility.
  • Algorithm: The algorithm adds Laplace noise to subtree demand counts and opens facilities according to noisy thresholds at each tree level.
  • Guarantees: The algorithm preserves ǫ-differential privacy and outputs a solution with cost OPT · O(log n log ∆) · log ∆.

8 Combinatorial Public Projects (Submodular Maximization)

The CPP section privately maximizes the aggregate submodular valuation of k resources using exponential-mechanism selection, achieving near-greedy quality with differential privacy.

  • CPP selects k resources to maximize the sum of private, non-decreasing submodular valuation functions submitted by n agents.
  • Algorithm: The efficient algorithm greedily selects resources, biasing each choice with the exponential mechanism toward larger marginal aggregate utility.
  • Utility: Except with probability O(1/poly(n)), the algorithm returns quality at least (1 − 1/e)OPT − O(k log m/ǫ′).
  • Privacy: The CPP algorithm preserves (ǫ′(e − 1) ln(e/δ), δ)-differential privacy for any δ ≤ 1/2.
  • Parameterization: Setting ǫ′ = ǫ/k yields ǫ-differential privacy and expected utility at least (1 − 1/e)OPT − O(k^2 ln m/ǫ).
  • Truthfulness: Differential privacy implies (2ǫ + δ)-approximate truthfulness, contrasting with the stronger inapproximability result for polynomial-time exactly truthful mechanisms.

9 Steiner Forest

For Steiner network, the paper outputs an oblivious tree that implicitly connects private terminal pairs, preserving their privacy perfectly while incurring logarithmic expected cost.

  • The private input is a subset R of source-sink terminal pairs that must be connected by a minimum-cost edge set.
  • Implicit Solution: The algorithm outputs a tree, and each terminal pair uses its unique tree path; their union defines the implicit solution.
  • Guarantees: The FRT tree construction is oblivious to R, preserves privacy perfectly with ǫ = 0, and gives expected cost O(log n) · OPT.

10 Private Amplification Theorem

This section develops private amplification for mechanisms that achieve a target quality with nontrivial probability, improving utility while controlling privacy and efficiency. A simpler repetition strategy incurs a logarithmic loss, motivating a more sophisticated construction.

  • Private Amplification Theorem: Repeating a private mechanism and selecting among its outputs can amplify the probability of obtaining quality at least Q.The construction also adds dummy outcomes and uses the exponential mechanism to select the final output.
  • Private Amplification Theorem: The basic repetition approach makes T calls, achieves utility failure probability 2^-T, and incurs privacy degradation proportional to T.Its stated properties are utility at least 1 − 2^-T, efficiency of T calls, and privacy parameter ǫT.
  • Private Amplification Theorem: Reducing failure probability to inverse polynomial by basic repetition requires logarithmic T and can cause an additional logarithmic approximation loss when Q is inversely proportional to ǫ.The section presents the more sophisticated amplification theorem as improving on this trade-off.
  • Private Amplification Theorem: The Private Amplification Theorem assumes success probability at least p and provides a mechanism with controlled utility, privacy, and calls to the original mechanism.The theorem applies to a sensitivity-1 query and permits arbitrary δ > 0 and ǫ′ in the stated range.
  • Private Amplification Theorem: The amplified mechanism selects from genuine and dummy outcomes through an exponential-mechanism score based on the quality query.The analysis bounds the probability of selecting a dummy outcome using the expected number of genuine outputs meeting the quality threshold.
  • Private Amplification Theorem: The privacy proof compares neighboring inputs using query sensitivity and differential privacy of the original mechanism, then establishes that the resulting mechanism satisfies (ǫ + 8ǫ′)-differential privacy.The proof controls the relevant denominator through concentration and expectation bounds.

A Unweighted Vertex Cover Algorithm: An Alternate View

This alternate vertex-cover implementation runs a privacy-adjusted proportional-to-degree process before randomly ordering the remaining vertices. Its utility analysis couples the private process to a non-private 2-approximation algorithm.

  • A Unweighted Vertex Cover Algorithm: An Alternate View: For the first αn rounds, the algorithm selects each vertex with probability proportional to d(i) + 1/ǫ, then outputs the remaining vertices in random order.The additive term is interpreted as 1/ǫ hallucinated edges per vertex.
  • A Unweighted Vertex Cover Algorithm: An Alternate View: Selecting a vertex removes it and its adjacent real and hallucinated edges, equivalently choosing a random edge and then a random real endpoint.The hallucinated edges of other vertices remain unchanged.
  • A Unweighted Vertex Cover Algorithm: An Alternate View: The privacy analysis represents the first αn rounds with weights 1/ǫ and the remaining rounds with infinite weights.This weighting viewpoint is used to analyze privacy similarly to the earlier vertex-cover theorem.
  • A Unweighted Vertex Cover Algorithm: An Alternate View: The utility analysis couples real-edge selections with a non-private algorithm that selects an arbitrary edge and a random endpoint, yielding a 2-approximation.The private algorithm’s selected cover contains the coupled algorithm’s cover.
  • A Unweighted Vertex Cover Algorithm: An Alternate View: The algorithm’s cost equals the number of selected vertices that still have nonzero real degree, split between the first αn steps and the random-order phase.These quantities are denoted I1 and I2, with total cost I1 + I2.
  • A Unweighted Vertex Cover Algorithm: An Alternate View: Conditioned on selecting an interesting vertex in the first phase, the probability that the selected edge is real is at least ǫ′ = 1/(1 + 1/ǫ).The analysis relates the expected number of coupled non-private steps to OPT through E[R] ≤ 2OPT.

B Missing Proofs

The missing proofs establish exponential tail bounds for adaptive probabilistic processes and connect those bounds to private weighted set cover and submodular minimization analyses.

  • B Missing Proofs: Lemma B.1 bounds the tail of a process driven by adaptively chosen Bernoulli probabilities: Pr[Y > q] ≤ exp(−q).The proof proceeds by reverse induction over the rounds.
  • B Missing Proofs: The randomized weighted set-cover algorithm is represented by first deciding whether to cover an element via a coin toss, then sampling the set conditionally.This representation maps the algorithm to the probabilistic process of Lemma B.1.
  • B Missing Proofs: A generalized process replaces Bernoulli trials with adaptively chosen distributions on [0, 1], updating the survival variable by Zi+1 = Zi − RiZi.The associated random variable is defined using the weighted expected reductions across rounds.
  • B Missing Proofs: Lemma B.2 extends the exponential tail bound to the generalized process, giving Pr[Y > q] ≤ e exp(−q).The proof establishes a stronger conditional claim by reverse induction and uses convexity to complete the bound.
Loading 0903.4510v2…