Abstract: Differential privacy enables organizations to collect accurate aggregates over sensitive data with strong, rigorous guarantees on individuals' privacy. Previous work has found that under differential privacy, computing multiple correlated aggregates as a batch, using an appropriate strategy, may yield higher accuracy than computing each of them independently. However, finding the best strategy that maximizes result accuracy is non-trivial, as it involves solving a complex constrained optimization program that appears to be non-linear and non-convex. Hence, in the past much effort has been devoted in solving this non-convex optimization program. Existing approaches include various sophisticated heuristics and expensive numerical solutions. None of them, however, guarantees to find the optimal solution of this optimization problem. This paper points out that under (ε, δ)-differential privacy, the optimal solution of the above constrained optimization problem in search of a suitable strategy can be found, rather surprisingly, by solving a simple and elegant convex optimization program. Then, we propose an efficient algorithm based on Newton's method, which we prove to always converge to the optimal solution with linear global convergence rate and quadratic local convergence rate. Empirical evaluations demonstrate the accuracy and efficiency of the proposed solution.
Introduction
Differential Privacy (DP) is the gold standard for releasing aggregate statistics while protecting individual privacy. A key challenge in DP is maximizing the utility (accuracy) of the released data. Researchers have discovered that answering a batch of correlated queries—a "workload"—can be done more accurately by answering a different, carefully chosen set of queries—a "strategy"—and then mathematically reconstructing the original answers.
However, finding the best strategy has historically been formulated as a non-linear, non-convex optimization problem. Because the "error surface" was thought to be full of local traps, existing solutions relied on unstable heuristics or expensive numerical methods that could not guarantee finding the most accurate possible strategy.
The Convexity Breakthrough
This paper presents a significant mathematical advancement: under $(\epsilon, \delta)$-differential privacy (approximate DP), the strategy-searching problem can be reformulated into a simple and elegant convex optimization program. By shifting the perspective to the solution matrix $X = A^T A$, the authors transform a previously "hard" problem into one that is mathematically tractable and efficiently solvable.
To solve this new convex formulation, the authors introduce the Convex Optimization Algorithm (COA). Key features include:
- Newton’s Method: Unlike previous first-order methods, COA uses second-order information (the Hessian), allowing it to achieve a globally linear and locally quadratic convergence rate.
- Matrix Lifting: The derivation involves a non-trivial semi-definite programming "lifting" technique to remove quadratic terms.
- Homotopy Algorithm: To handle cases where the workload matrix isn't full rank, they use a homotopy approach, starting with a regularized version of the problem and gradually steering it toward the original objective.
Convergence and Performance
A defining feature of COA is its stability and speed. Unlike previous state-of-the-art methods like the Low-Rank Mechanism (LRM), which were non-monotone and could fluctuate during optimization, COA is a "greedy descent" algorithm that improves accuracy in every iteration.
As illustrated in the convergence plots above, COA typically converges in fewer than 20 iterations across various real-world datasets (Search Log, Net Trace, Social Network, and UCI Adult). The Frobenius norm of the gradient $G$—a measure of the optimality gap—drops precipitously, confirming the algorithm's theoretical convergence guarantees.
Key Results
- Guaranteed Optimality: COA is the first polynomial-time algorithm that guarantees finding the global optimum for this problem under approximate DP.
- Accuracy: COA consistently matches or outperforms all existing methods (GM, WM, HM, ESM, AM, and LRM). In some cases, it reduces error by over two orders of magnitude compared to the naive Gaussian Mechanism.
- Efficiency: Thanks to its quadratic convergence, COA is highly scalable. Its complexity is tied to the number of unit counts ($n$), not the number of queries ($m$), making it efficient for massive workloads.
Conclusion and Future Work
By revealing the underlying convexity of the strategy-selection problem, this work provides a robust and efficient foundation for private data analysis. While the current formulation is strictly for $(\epsilon, \delta)$-differential privacy, future work may explore extending this convex approach to "pure" $\epsilon$-DP (Laplace noise) and incorporating data-dependent information to further enhance utility.
Summary updated