Differentially private convex optimization with piecewise affine objectives

Shuo Han, Ufuk Topcu, George J. Pappas

Abstract

As cyber-physical systems increasingly rely on granular user data to optimize infrastructure—ranging from smart power grids to intelligent traffic management—the risk of exposing sensitive individual information grows. This paper addresses the challenge of solving convex optimization problems under the framework of Differential Privacy (DP). Specifically, we focus on piecewise affine objective functions, where sensitive data is embedded within the constant offsets of the objective. We evaluate several privacy-preserving mechanisms and introduce a novel Private Subgradient Method. This iterative approach utilizes the Exponential Mechanism at each step to navigate the optimization landscape while maintaining rigorous privacy guarantees. Our results demonstrate that this iterative method consistently outperforms standard noise-injection techniques, offering a scalable and robust solution for private optimization in modern data-driven systems.

Introduction

In the era of the Internet of Things (IoT) and smart infrastructure, optimization is the engine behind efficiency. Operators of cyber-physical systems (CPS) must solve complex mathematical problems to balance supply and demand, manage congestion, and reduce costs. However, the inputs to these problems often consist of high-resolution data from individual users, such as minute-by-minute electricity consumption.

Traditional methods of data protection, such as simple anonymization, have proven insufficient against modern de-anonymization attacks that leverage side information. Consequently, there is a critical need for optimization frameworks that provide formal, mathematical guarantees of privacy. This paper explores the application of Differential Privacy (DP) to a specific but widely used class of problems: convex optimization with piecewise affine objectives.

Problem Formulation: Piecewise Affine Objectives

Piecewise affine functions are characterized by an objective that is the maximum of several linear functions, visually resembling a series of flat "panes" or a folded sheet of paper. In many practical scenarios, the sensitive parameters of the problem are located in the constant offsets ($b_i$) of these linear segments.

The goal is to minimize this objective function without allowing an adversary to reverse-engineer the private offsets from the published solution. The challenge lies in the fact that the optimal solution is inherently sensitive to the input data; a small change in a single user's data could shift the minimum point, potentially leaking information about that user.

Privacy Mechanisms and Methodology

To address this, the paper evaluates four distinct approaches to injecting controlled noise to satisfy the requirements of Differential Privacy:

  1. Laplace Mechanism on Data: Noise is added directly to the sensitive input data ($b_i$) before the optimization problem is solved. While simple, this can lead to significant suboptimality if the noise shifts the problem structure too drastically.
  2. Laplace Mechanism on Solution: The problem is solved exactly using the raw data, and noise is added to the final result. This approach is limited by the "sensitivity" of the optimal solution, which can be high in complex landscapes.
  3. Exponential Mechanism: This non-iterative approach treats the objective function as a probability map. Instead of selecting the absolute minimum, it samples a solution from the search space, favoring regions with lower costs.
  4. Private Subgradient Method: The core innovation of this work is an iterative algorithm. In a standard subgradient method, the algorithm takes steps in the direction of the steepest descent. In the private version, the Exponential Mechanism is employed at every iteration to choose a private step direction. This method relies on the Sequential Composition Theorem, which allows for the strategic allocation of a "privacy budget" across multiple steps.

Theoretical Insights

Exact Sensitivity Analysis

A cornerstone of the paper’s theoretical contribution is the proof that for piecewise affine functions, the global sensitivity—the maximum change in the function caused by a single data point—is exactly equal to the maximum possible change in the data offsets ($b_{max}$). This finding simplifies the application of DP mechanisms, as it provides a clear bound for the required noise scale.

The Iteration Trade-off

In traditional optimization, increasing the number of iterations generally leads to higher accuracy. However, in a differentially private setting, more iterations require the privacy budget ($\epsilon$) to be spread thinner, resulting in more noise per step. The authors identify a "sweet spot"—a mathematically defined optimal number of iterations where the progress toward the minimum is maximized before the cumulative noise becomes counterproductive.

Robustness to Biased Noise

While standard stochastic optimization proofs often assume "unbiased" noise (noise that averages to zero), the noise introduced by the Exponential Mechanism in the Private Subgradient Method is inherently biased. Despite this, the authors demonstrate that the algorithm remains remarkably robust, converging effectively in practical applications.

Experimental Results

Using synthetic datasets generated from Gaussian distributions and constrained within $d$-dimensional hypercubes, the authors conducted 1,000 simulations per test to evaluate the "suboptimality gap" (the difference between the private solution and the true minimum).

  • Performance: The Private Subgradient Method consistently achieved the lowest suboptimality gap compared to the Laplace and standard Exponential mechanisms.
  • Scalability: As the search space (the constraint set) expanded, the error in the Private Subgradient Method grew at a significantly slower rate than its counterparts, suggesting better performance for high-dimensional problems.
  • Privacy-Utility Trade-off: The results quantify the relationship between the privacy parameter $\epsilon$ and accuracy. As $\epsilon$ increases (relaxing privacy), the error decreases, providing a clear metric for system designers to balance user privacy against operational efficiency.

Conclusion and Future Work

This research demonstrates that iterative, privacy-aware algorithms like the Private Subgradient Method are superior to one-shot noise injection for piecewise affine optimization. While the current theoretical error bounds are noted to be conservative (the algorithm performs better in practice than the math currently predicts), they provide a solid foundation for private CPS operations.

Future research will focus on tightening these theoretical bounds and extending the iterative private mechanism to more general linear programs and non-linear convex problems. Additionally, the study of biased noise in optimization remains a fertile ground for developing new convergence theories in the field of private machine learning and control.

Summary updated

BibTeX
@inproceedings{han2014differentially,
  author = {Shuo Han and Ufuk Topcu and George J. Pappas},
  title = {{Differentially private convex optimization with piecewise affine objectives}},
  booktitle = {CDC},
  year = {2014},
  url = {https://openreview.net/forum?id=M8p4TiSR07},
}
Figure