Overview
This paper extends "objective perturbation"—a powerful technique for differential privacy—to non-convex optimization problems. By introducing a clever "normalization trick" and leveraging non-private optimization oracles (like integer program solvers), the authors provide two new algorithms that outperform standard convex surrogate methods when training on sensitive data.
The Challenge of Private Non-Convex Optimization
In differentially private (DP) machine learning, researchers face a frustrating trade-off. On one hand, general-purpose tools like the Exponential Mechanism work for any problem but are computationally intractable because they require searching through every possible parameter combination. On the other hand, efficient tools like Objective Perturbation traditionally require the objective function to be "well-behaved"—specifically, convex and smooth.
This leaves a massive gap: how do we privately solve non-convex problems (like training a classifier with a 0/1 loss function) without resorting to exponential time? The authors tackle this by asking if we can use "oracles"—existing high-performance, non-private heuristics like Mixed-Integer Programming (MIP) solvers—to build efficient, private algorithms for non-convex tasks.
Proposed Methods
The authors introduce two primary algorithms to bridge this gap:
- OPDisc (Objective Perturbation over Discrete Spaces): Designed for discrete parameter sets, this algorithm's core innovation is the Normalization Trick. Standard objective perturbation adds a random linear term to the loss function. However, without convexity, a tiny change in the data could cause the optimal solution to jump wildly across the map, leaking private information. By mapping the parameters onto a unit sphere in a higher dimension before perturbing, the authors "stabilize" the optimization, ensuring that the output remains private even without convexity.
- OPSamp (Objective Perturbation via Sampling): This algorithm works for continuous spaces using a "Follow-the-Perturbed-Leader" (FTPL) approach. It calls an optimization oracle multiple times with different random noises, averages the results, and adds a final layer of Laplace noise. Crucially, its privacy guarantee only requires the loss function to be Lipschitz-continuous, not convex.
Key Insights
- Stability via Geometry: The "Normalization Trick" is a critical breakthrough. By forcing all parameter vectors to have the same length (mapping them to a sphere), the authors prevent the noise from being "outvoted" by the scale of the parameters. This geometric constraint provides the stability needed for privacy that convexity usually provides.
- Direct vs. Surrogate Optimization: In non-private ML, convex surrogates (like logistic loss) are often used because they are easier to solve than 0/1 loss. However, the authors show that under the "noise" of differential privacy, the error introduced by a surrogate can actually be worse than the difficulty of solving the original non-convex problem.
- Oracle Efficiency: The paper reinforces the idea that we don't need to reinvent the wheel for privacy. If we have a "black box" that is good at solving hard optimization problems, we can wrap it in a specific noise-adding framework to make it private.
Experimental Results
The researchers evaluated their approach using the Adult dataset (from the UCI Machine Learning Repository), a standard benchmark derived from US Census data, to predict whether an individual earns over $50k/year. They used the Gurobi MIP solver as their optimization oracle to directly minimize the non-convex 0/1 classification loss on a balanced subset of 15,682 records.
- Superior Accuracy: As shown in the figure above, OPDisc significantly outperformed private logistic regression (the standard convex baseline) across various privacy budgets ($\epsilon$).
- Lower Variance: OPDisc demonstrated much more stable performance, evidenced by the tighter error bars (lower variance in accuracy across runs) compared to previous state-of-the-art methods like RSPM.
- Practicality: While non-convex optimization is NP-hard in the worst case, modern solvers like Gurobi could solve the perturbed objectives for the Adult dataset in a reasonable timeframe, proving the method is not just theoretically sound but practically viable.
Limitations and Future Work
- Discretization Dependency: OPDisc requires a discrete parameter space. While the authors show how to discretize a continuous space, the "fineness" of this grid creates a trade-off between accuracy and the amount of noise required.
- Convexity for Utility: While the continuous algorithm (OPSamp) is private for non-convex functions, the authors could only prove it is accurate (maintains utility) when the function is convex. Extending utility proofs to the non-convex case remains an open challenge.
- Scalability: Integer programming solvers are powerful but have limits. Scaling these exact non-convex methods to deep learning or very high-dimensional datasets (thousands of features) would likely require more specialized oracles.
Summary updated